백준 11066 파일 합치기 - 파이썬

문제.

 

풀이.

정답률이 50퍼가 넘던데 문제가 너무 어려웠다.

크누스 최적화라는 알고리즘을 사용해서 풀었다.

크누스 최적화는 특수한 조건일 때 시간 복잡도를 O(n^3)에 O(n^2)까지 줄일 수 있는 알고리즘이다.

우선 크누스 최적화 알고리즘을 적용할려면 다음과 같은 조건을 만족해야한다.

 

사각 부등식: C[a][c] + C[b][d] <= C[a][d] + C[b][c] (a <= b <= c <= d)

단조성: C[b][c] <= C[a][d]  (a <= b <= c <= d)

점화식: DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j] (i < k < j)

 

pypy3로 제출을 했다.

 

소스코드.

import sys

def knuth_optimizer():
    dp = [[0 for col in range(file_count+1)] for row in range(file_count+1)]
    file_sum = [0] * (file_count+1)

    for i in range(1, file_count+1):
        file_sum[i] = file_sum[i-1] + file_list[i]

    # 파일의 길이가 1일 경우에는 비용이 들지 않으므로 2부터 시작
    for i in range(2, file_count+1):
        for j in range(1, file_count+2-i):
            dp[j][j+i-1] = min([dp[j][j+k] + dp[j+k+1][j+i-1] for k in range(i-1)]) + (file_sum[j+i-1] - file_sum[j-1])

    return dp[1][file_count]

input = sys.stdin.readline

tc = int(input())

for i in range(tc):
    file_count = int(input())
    file_list = [0] + list(map(int, input().split()))
    print(knuth_optimizer())