다이나믹 프로그래밍시 테이블 계산 순서

문제: https://www.acmicpc.net/problem/9520

다이나믹 프로그래밍을 코딩하는 방식은 크게 재귀와 루프로 나뉜다. 재귀 방식은 일종의 지연 평가(lazy evaluation)를 구현한다. (i,j) 항을 참조했는데 평가되지 않았다면 평가하여 반환하고, 이미 평가되었다면 그대로 값을 반환한다. 루프 방식은 for/while로 루프를 돌며 DP 테이블을 채운다. 문제에 따라 무엇을 써도 상관 없는 경우가 있고 재귀나 루프 중 하나가 훨씬 편한 경우도 있다. 나는 루프를 선호한다.

이 문제의 경우 방문 순서를 그리면 1~(n-1)번 도시들은 무조건 n번 도시의 왼쪽이나 오른쪽에 통째로 있어야 한다. 따라서 점화식을 다음과 같이 세울 수 있다.

    dp[i][j] = 도시 1~i를 방문하는데 i에서 시작하고 j로 끝날 때의 최소 비용 (i > j)

    dp2[i][j] = 도시 1~i를 방문하는데 i에서 끝나고 j로 시작할 때의 최소 비용 (i > j)

답은 모든 1 <= i <= n-1에 대해 dp[n][i], dp2[n][i] 들중 최솟값이다.

이제 점화식을 만들어보자. dp[i][j]를 계산하려면 도시 1~(i-1)을 방문할 때의 비용 + 도시 i를 방문하는 비용 중 최솟값을 찾으면 될 것 같다. 따라서 도시 1~i를 방문하는데 i에서 시작하여 어떤 도시 k로 넘어가고 마지막으로 도시 j에서 끝나는 경우를 생각해보자.

dp[i][j] = cost[i][k] + (도시 1~(i-1)을 방문하는데 k에서 시작하고 j에서 끝날 때 최소 비용) = ???

이 DP 테이블로는 빨갛게 표시한 항을 계산할 수가 없다. 처음에는 dp[i][j]를 잘못 잡은 줄 알았다. 하지만 도시 1~i에 대한 해를 가지고 도시 1~(i+1)에 대한 해를 구하는 것을 생각해보자.

dp[i][j]를 알면 dp[i+1][j]와 dp2[i+1][i]를 계산할 수 있다. 즉 테이블의 인덱스 (i,j)인 원소를 계산하기 위해 (i-1,j), (i,j-1)처럼 인덱스가 작은 원소를 참조하는 것이 아니라, 인덱스가 (i,j)인 원소를 가지고 인덱스가 더 큰 원소를 갱신하는 것이다.

dp[i][j] = dp2[i][j] = INF로 초기화

// DP: base case

dp[2][1] = dp2[2][2] = cost[2][1];

dp[2][2] = dp2[2][1] = cost[1][2];

// DP: recursive case

for(int i=2; i<n; i++){

    for(int j=1; j<i; j++){

        dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost[i+1][i]);

        dp2[i+1][i] = min(dp2[i+1][i], dp[i][j] + cost[j][i+1]);

        dp2[i+1][j] = min(dp2[i+1][j], dp2[i][j] + cost[i][i+1]);

        dp[i+1][i] = min(dp[i+1][i], dp2[i][j] + cost[i+1][j]);

    }

}

int soln = min(dp[n][1], dp2[n][1]);

for(int i=2; i<=n; i++){

    soln = min(soln, min(dp[n][i], dp2[n][i]));

}

이 방법은 인덱스 계산이 복잡해서 코딩을 실수할 여지가 크다. (실제로 인덱스에 오타를 내서 오답을 받았다) 다음 점화식은 acmicpc.net의 운영자인 백준님이 제시한 것으로 DP 테이블도 하나만 쓰고 계산이 더 간단하다.

    dp[i][j] = 도시 1 ~ max(i,j)를 방문하는데 i에서 시작하고 j에서 끝날 때 최소 비용

이렇게 설정하면 dp[i][j]를 가지고 dp[max(i,j)+1][j]와 dp[i][max(i,j)+1]을 갱신할 수 있다.