BOJ 13261 탈옥 (분할정복 동적계획법 최적화)

https://www.acmicpc.net/problem/13261

13261번: 탈옥

컨벡스 홀 최적화 각인줄 알고 식 유도하려고 뻘짓하다가 알고 보니 너무 당연하게 분할정복 최적화였던 문제.

분할정복 최적화를 적용할 수 있는 케이스는 아래와 같다.

• 점화식: DP[i][j] = min { DP[i-1][k] + C[k][j] } ( k < j )
• C[k][j] 는 monge array
  • C[a][c] + C[b][d] <= C[a][d] + C[b][c] ( a <= b <= c <= d)

위의 조건을 만족하면, opt(i, j)를 위의 점화식을 최적으로 만드는 가장 작은 k라고 정의 했을 때, 모든 i, j 쌍에 대해서 다음이 성립한다.

• opt(i, j-1) < opt(i, j)  (이 조건이 중요하다)

따라서, 어떤 i, j 쌍에 대해서 opt(i, j)를 알고 있다면 opt(i, j')을 계산 하는데 위의 식을 사용하여 최적화를 할 수 있다. 문제의 j 구간을 반씩 나눠서 분할 정복을 하면 O(n * m log m)에 문제를 해결 할 수 있다. ( i <= n, j <=m)

 

탈옥 문제의 점화식은 아래와 같다.

• DP[i][j] = min { dp[i-1][k] + (sum[j] - sum[k]) * (j - k) }
•   = min { dp[i-1][k] + C[j][k] } where C[j][k] = (sum[j] - sum[k]) * (j - k) 

위의 조건 opt(i, j-1) < opt(i, j) 을 만족 하므로, 분할정복 최적화를 적용할 수 있다.

https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html

Divide and Conquer DP - Competitive Programming Algorithms