백준 11066번: 파일 합치기 (Python, PyPy3)

접근

굉장히 어려운 dp문제였다. 풀이 방법을 생각해내는데에도 많은 시간을 썼고, 최적화를 위해 추가적인 방법을 찾는 과정에서 다른 문제 풀이를 보고 이해하는데도 시간이 많이 걸렸다.

결론적으로 말하자면 dp[i][j]에 i번째부터 j번째 챕터를 합치는 최소 비용을 저장하게 된다.

그렇다면 dp[0][n]의 값(0번 챕터부터 n번 챕터까지 합치는 최소 비용)은
dp[0][0] + dp[1][m]
dp[0][1] + dp[2][m]
...
dp[0][n - 2] + dp[n - 1][m]
dp[0][n - 1] + dp[n][m]
값 중 하나일 것이다.

이러한 방법으로 코드1의 식을 얻었지만 Python으로는 시간 초과, PyPy3으로 풀었을 때 간신히 시간안에 들어올 수 있었다. 아무래도 3중 for문을 돌아 O(N^3)의 시간복잡도를 가지기 때문인 것으로 보인다.

추가적인 최적화 방법을 찾기 위해 찾아본 결과 Knuth's Optimization이라는 최적화 방법에 대해 알게되었다.

참고: 11066. 파일합치기

Knuth's Optimization를 통해 다음의 특별한 조건을 충족할 때 DP문제의 최적화가 가능하다.

1. DP 점화식의 꼴
$$ DP[i][j] = min_{i<k<j}(DP[i][k] + DP[k][j]) + C[i][j] $$

2. 사각부등식
$$ C[a][c] + C[b][d] \leq C[a][d] + C[b][c],(a\leq b\leq c\leq d) $$

3. 단조성
$$ C[b][c] \leq C[a][d],(a\leq b\leq c\leq d) $$

위의 조건을 만족하면, \( A[i][j] = D[i][j] \)가 최소가 되기 위한 가장 작은 k라고 했을 때 아래의 식을 만족한다.

$$ A[i][j - 1] \leq A[i][j] \leq A[i + 1][j] $$

이를 통해 k의 값이 제한되고, 결과적으로 O(N^3) 문제를 O(N^2)의 문제로 최적화 할 수 있다.

기존 코드로 PyPy3에서 간신히 통과했던 코드가 최적화를 통해 Python3으로도 통과되었다. PyPy3의 경우엔 기존보다 시간이 1/3로 단축되었다.

코드

코드1

import sys

m = int(sys.stdin.readline())
for ___ in range(m):
    n = int(sys.stdin.readline())
    pages = list(map(int, sys.stdin.readline().split()))
    dp = [[0 for __ in range(n)] for _ in range(n)]
    for x in range(1, n):
        for i in range(n - x):
            j = i + x
            dp[i][j] = 999999999999
            tmp = sum(pages[i: j + 1])
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + tmp)
    print(dp[0][n - 1])

코드2 (Knuth's Optimization)

import sys

m = int(sys.stdin.readline())
for ___ in range(m):
    n = int(sys.stdin.readline())
    pages = list(map(int, sys.stdin.readline().split()))
    dp = [[0 for __ in range(n)] for _ in range(n)]
    knuth = [[0 for __ in range(n)] for _ in range(n)]
    for i in range(n):
        knuth[i][i] = i
    for x in range(1, n):
        for i in range(n - x):
            j = i + x
            dp[i][j] = 999999999999
            tmp = sum(pages[i: j + 1])
            for k in range(knuth[i][j - 1], knuth[i + 1][j] + 1):
                if k < n - 1 and dp[i][j] > dp[i][k] + dp[k + 1][j] + tmp:
                    dp[i][j] = dp[i][k] + dp[k + 1][j] + tmp
                    knuth[i][j] = k
    print(dp[0][n - 1])

더 생각해 볼 것?

두번째 동적계획법 단계에 들어오면서 난이도가 확 오른 느낌이다. 완전히 이해하여 다음 문제에는 똑같이 헤메지 않도록 해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!