문제 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 처음엔 단순한 그래프 문제로 생각했는데, 잘 풀리지 않았다. 곰곰히 생각해보니 이전에 프로그래머스에서 풀었던 등굣길 문제와 유사했다. 좌표 (0, 0)부터 (n-1, n-1)까지 순회하며 현재 좌표(x, y)에서 오른쪽과 아래쪽으로 갈 수 있는지 검사하고, 만약 갈 수 있다면 dp[nx][ny]에 dp[x][y]를 더해준다. 이때 dp[y][x] == 0이면 건너뛰는 방식으로 최적화를 해줄..
문제 www.acmicpc.net/problem/2644 풀이 BFS로 풀이했다. 거리(촌수)를 구해야 할 두 노드가 정해져 있기 때문에 시작 노드만 큐에 넣고 탐색을 했다. 코드 import sys, collections def bfs(start, end): q = collections.deque([]) q.append([start,0]) visited[start] = 1 while q: cur, cnt = q.popleft() if cur == end: print(cnt) return for adj in g[cur]: if not visited[adj]: visited[adj] = 1 q.append([adj,cnt+1]) print(-1) n = int(sys.stdin.readline().stri..
문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유사한 문제들은 많이 풀어보았다. 1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 점화식은 다음과 같다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3
문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 이전에 풀었던 오르막 수 문제의 쉬운 버전 문제다. dp[n][0] = 0으로 끝나는 n자리 이친수의 개수 dp[n][1] = 1로 끝나는 n자리 이친수의 개수 문제에 주어진 조건을 살펴보자. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 1번 조건에 의해 dp[1][0] = 0, dp[1][1] = 1이 성립..
문제 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 가장 큰 증가 부분 수열 문제의 응용 문제다. 이중 for문을 두 번 구성하여 dp[n][0]엔 왼쪽부터 증가하는 가장 긴 부분 수열의 길이를 기록하고, dp[n][1]엔 오른쪽부터 증가하는 가장 긴 부분 수열의 기록을 기록한다. 중복으로 겹쳐지는 부분이 있기 때문에 해를 구할 땐 1을 빼줘야 한다. 코드 import sys n = int(sys.stdin.readline().strip()) a = [int(x) for..
