메이쁘

www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 안녕하세요. 처음에 경로의 최대 개수를 구하는 줄 알고 풀었다가 문제를 다시 보니 밑줄 친 부분과 같이 종료 지점이 따로 존재하는 게 아니라 H(구멍)에 도착하거나, 맵 밖으로 벗어나면 종료하는 것이기 때문에 별도의 경로가 존재하지 않다는걸 깨달았습니다. 즉, 매 지점마다 4방향으로 튈 수 있다는 뜻이므로 최대 4^(50*50) 의 경우의 수가 존재하고, 이는 곧 시간 초과를 불러옵니다. 따라서, DP 를 활용..

www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파� www.acmicpc.net 안녕하세요. 문자열 문제인줄 알고 접근했는데 그리디였던 문제입니다. 해당 문제의 그리디 접근 방식은 간단합니다. 매커니즘 1) 가장 최소비용으로 살 수 있는 숫자와 최소 비용을 별도로 저장합니다. 2) 가장 최소비용으로 살 수 있는 숫자의 최대 개수를 구합니다. 3) 가장 최소비용으로 살 수 있는 숫자가 0인지 아닌지 체크합니다. (0만 다사면은 숫자가 성립되지 않으므로) *** 가장 최소비용으로 살 ..

www.acmicpc.net/problem/5015 5015번: ls 첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 �� www.acmicpc.net 안녕하세요. 이 문제는 처음에 패턴 보고 정규표현식? 개꿀! 해서 Pattern과 Matcher를 사용했는데 보기좋게 시간초과를 당했었습니다.. 즉, 단순한 정규표현식 문제가 아니라는 뜻인데요. 도저히 머리가 안굴려져서 고민고민끝에 구글신을 찾았습니다... 그러다가! DP와 완탐 재귀를 사용한 방법을 보게 되었는데요.. 머리 한대 강하게 맞은 것처럼 얼얼했습니다.. 이렇게 생각해서 풀 수..

www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 안녕하세요. 다익스트라 문제입니다. 제가 처음에 생각한 해결 방법은 모든 지름길을 찾아서 다익스트라로 지름길의 도착지점의 값을 변경한 후 각 지름길 도착 지점 + 도착 지점까지의 남은 거리 의 최소를 찾으려고 했습니다만 예외 케이스가 있었나봅니다.. 결과는 틀렸습니다. 그래서 해설을 조금 참고했습니다. 맙소사! 다르게 생각하니, 쉽게 해결할 수 있는 것을... 그건 바로, 거리를 시작 지점에서 1씩 ..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 안녕하세요. DP와 LIS 알고리즘을 사용하여 해결한 문제입니다. LIS 알고리즘은 기억하시나요? 이는 증가하는 부분 수열 알고리즘 입니다. 뭐.. 이를 응용해서 길이나, 수열의 최댓값/최솟값 등을 구할 수 있죠. 아무튼 이 문제를 푼 지 조금 오래되서 풀이법이 가물가물 하지만 최대한 복기해가며 적어보겠습니다. 우선, 아래 포스팅의 문제와 비슷한 풀이방법입니다. maivve.tistory.com/234 (JAVA) 백..

www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 �� www.acmicpc.net 안녕하세요. 바로 풀자마자 작성하는 게 아니라, 한 일주일 지나서 작성하는거라 풀이 방법이 가물가물하네요.. 핵심은 해당 지점에서 목적지까지 갈 수 있는 경로의 개수 를 구하는 것입니다. 맵에서 해당 지점의 숫자는 오른쪽 또는 아래쪽 으로 갈 수 있는 칸의 개수 입니다. 이를 활용해서 경로를 어떻게 구하나 고민하다가, DFS 를 사용했습니다. 하지만, 이렇게 DFS만 사용한다면, 쉬운 문제였곘죠..

www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 안녕하세요. 이 문제는 트라이 알고리즘을 사용하는건데, 약간의 기출변형이 있어 고민이 필요한 문제입니다. 우선 단어들을 다 트라이에 넣고, (이 때 별도의 리스트에 단어들을 저장해둡니다. 그 이유는 이따 하나씩 꺼내면서 버튼 횟수를 확인해야하기 때문입니다.) 한 단어씩 리스트에서 탐색하며 버튼 횟수를 count 합니다. 버튼 횟수 count하는 방법은 contains 함수를 만들어서 해결했는데, 1) 자식 노드의 개..

www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 � www.acmicpc.net 안녕하세요. DFS 알고리즘 문제입니다. 크게 어렵지 않고, 헷갈리는 부분만 있습니다. 놓을 수 있는 선물 하나 당 하나의 사이클 입니다. 즉, DFS 알고리즘을 통해 사이클 여부를 찾고, 사이클인 경우 선물 갯수를 ++ 하면 됩니다. 또한, 탐색 여부를 Level 별로 따로 2차원 배열에 저장하여 DFS 탐색 시 한번도 방문하지 않은 곳 인 경우에만 계속 탐색을 ..

www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 안녕하세요. 조금 꼬아놓은 BFS 알고리즘 문제 입니다. 처음에는 단순히 양방향 그래프로 생각하고 진행했다가 O(1000^3) 및 메모리 초과로 인해 실패했었습니다. 이후, 다른 풀이자분의 소스코드를 참고해서 역 / 큐브 두 부분으로 나눠 배열을 만들어 저장한 다음, 특정 역에서 꺼낼 때, 역이 포함되어있는 큐브를 순회합니다. 이 때, 꺼낸 큐브의 모든 역을 순회하며 다음 역으로 이동..

www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 안녕하세요. solved.ac 골드1 문제로 다익스트라 알고리즘을 사용하여 해결했습니다. 장장 4시간에 걸쳐 끙끙대다 해결했는데요. 시간초과, 오답 등 여러 실패를 겪었습니다. 처음에는 1 ~ N까지 for문 순회하면서 각각의 지점을 정상으로 가정했을 때, 다익스트라를 통해 나온 최소 거리를 가지고 등산의 가치를 구했었습니다. 하지만 시간초과! 그 이유는 N이 100000일 경우, 다익스트라 알고리즘을..