백준 11066 [python]

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

import sys
T = int(input())

for i in range(T):
    K = int(input())
    chapter = list(map(int, sys.stdin.readline().split()))

    dp = [[[0, 0] for i in range(K)] for i in range(K)]
    for i in range(K):
        dp[i][i] = [chapter[i], 0]
    for i in range(K - 1):
        dp[i][i + 1] = [chapter[i + 1] + chapter[i]] * 2
    
    for i in range(2, K):
        for j in range(K - i):
            l = []
            for m in range(i):
                x1 = j
                y1 = j + m
                x2 = j + m + 1
                y2 = j + i
                l.append([dp[x1][y1][0] + dp[x2][y2][0], \
                sum(dp[x1][y1]) + sum(dp[x2][y2])])
            dp[j][j + i] = min(l, key=lambda x: x[1])
            
    print(int(dp[0][K - 1][1]))

먼저 점화식을 구해보려 고민했다. 내가 0~n까지 합치는 최소비용을 알더라도 n+1번 챕터를 고려해야 하는 상황이 되면, 처음부터 다시 구해서 0~n+1까지 합치는 최소비용을 구해야 한다. 따라서 모든 출발 챕터와 마지막 챕터를 구하며 문제를 풀어야 한다.

dp[i][j][0]: i챕터부터 j챕터까지 합치는 최소비용일 때, 그 파일의 체급(직전에 더해진 두 파일의 합)
dp[i][j][1]: i챕터부터 j챕터까지 합치는 최소비용

내가 만약 dp[0][3]를 구하려면, dp[0][0]+dp[1][3], dp[0][1]+dp[2][3], dp[0][2]+dp[3][3]중 합치는 최소비용이 가장 작은 것을 구해야 한다. 그 두 파일을 더한 값은 본인의 체급이 된다.

그런데 시간초과가 났다. for문이 세 번 돌아 o(n^3)인데, 구글링해보니 특수한 경우를 만족하면 o(n^3)를 o(n^2)로 바꾸는 크누스 최적화라는게 있단다. 어려워서 이해하지 못했는데, 이 알고리즘에 적용하면 세 번째 for문을 도는 범위를 상수번으로 바꿔준다.

import sys
T = int(input())

for i in range(T):
    K = int(input())
    chapter = list(map(int, sys.stdin.readline().split()))

    dp = [[[0, 0, 0] for i in range(K)] for i in range(K)]
    for i in range(K):
        dp[i][i] = [chapter[i], 0, 0]
    for i in range(K - 1):
        dp[i][i + 1] = [chapter[i + 1] + chapter[i]] * 2 + [i]
    
    for i in range(2, K):
        for j in range(K - i):
            l = []
            for m in range(dp[j][j + i - 1][2], dp[j + 1][j + i][2] + 1):
                x1 = j
                y1 = m
                x2 = m + 1
                y2 = j + i
                l.append([dp[x1][y1][0] + dp[x2][y2][0], /
                dp[x1][y1][0] +  dp[x1][y1][1] + dp[x2][y2][0] + dp[x2][y2][1], m])
            dp[j][j + i] = min(l, key=lambda x: x[1])
            
    print(int(dp[0][K - 1][1]))

dp[0][3]을 구하기 위해서는 min(dp[0][k] + dp[k + 1][3], (0 <= k < 4)를 구해야 하는데, 크누스 최적화에 의해 k의 범위가 n개가 아닌 상수개로 바뀌며 문제를 해결할 수 있었다.
dp[i][j]가 합치기 최소합일 때 위의 식에서 k값을 A[i][j]라고 할 때, k의 범위가 A[i][j - 1] <= A[i][j] = k <= A[i + 1][j]로 좁혀진다. 나는 A[i][j]값을 dp[i][j][2]에 저장해서 문제를 해결했다.