동적계획법

1 2 3 4 5 6 1 2 (2, 3) 3 (3, 5) 4 5 (5, 5) 6 문제이해 (1, 1)과 (n, n)에 있는 경찰차 두대가 최소거리로 사건들을 해결하는 방법과 거리를 출력하는 문제이다. 계획 이 문제가 어렵게 느껴지는 이유는 경찰이 현재 있는 위치에 따라 추가되는 거리가 계속해서 달라지기 때문이다. 따라서, 기존의 dp문제처럼 dist[n+1] = dist[n] + min(police1[n], police2[n])와 같은 점화식은 사용할 수 없다. 각 경우에 따라 거리가 달라지기 때문에 모든경우의 수를 탐색하는 방법을 생각할 수 있지만. 사건이 n개일 때의 경우의 수는 2^n개다. 사건이 3개일때의 경우의 수 111 112 121 122 211 212 221 222 사건의 개수가 1000개..

다른 코드 참조: O, 푼 횟수: 4 풀이과정 먼저 위의 문제와 같은 삼각형이 주어졌다고 가정할 때, 반복문을 이용해 최댓값을 구한다면 1. 7-3-8-2-4 2. 7-3-8-2-5 3. 7-3-8-7-5 ... 16. 7-8-0-4-5 이런식으로 전개되고 1~3에서와 같이 7-3-8 이 계속해서 반복되는 비효율이 발생한다. 따라서 동적 계획법을 이용해야 한다. 먼저, t[r][c] = 삼각형 r번째 줄, c번째 칸, dp[i][k] = t[i][k]까지의 합의 최댓값이라고 하자. 데이터가 추가된다고 할 때, 그 데이터에 도달할 수 있는 데이터는 다음과 같은 경우가 있다. 만약 삼각형의 양쪽 끝쪽 데이터의 경우(i번째 줄 0번 칸 or i번칸)를 제외하고 본다면, 추가되는 칸까지의 최대합은 dp[i-1]..