186. 11066(파일 합치기) - 파이썬

import sys
input = sys.stdin.readline

T = int(input())
result = []

for _ in range(T):
    K = int(input())
    page = [0] + list(map(int, input().split()))

    sumPage = [0 for _ in range(K+1)]
    for i in range(1, K+1):
        sumPage[i] = sumPage[i-1] + page[i]

    DP = [[0]*(K+1) for _ in range(K+1)]
    for i in range(2, K+1):
        for j in range(1, K+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)]) + (sumPage[j+i-1] - sumPage[j-1])

    result.append(str(DP[1][K]))

print("\n".join(result))

문제요약

모든 페이지를 합하는데 드는 최소 비용을 구하라

 

설명

DP의 가장 어려운 유형의 문제

이 문제의 기본적인 idea만 알아도 다른 문제에 많이 활용할 수 있다고 한다.

 

입력이 아래와 같을 때,

 

4

40 30 30 50

 

먼저 누적합을 구해주면 아래 list와 같다.

[0, 40, 70, 100, 150]

누적합을 구해주는 이유는 두 개의 파일을 합칠 때 필요한 비용(두 파일 크기의 합)을 

편하게 연산하기 위함이다.

 

이 문제는 DP를 정의하는게 정말 어렵다.

먼저 DP는 2차원 배열을 사용할 것이고,

DP[i][j]는 i에서 j까지 합하는데 필요한 최소 비용이 된다.

 

파일 한 개(파일의 길이 : 1)는 비용이 들지 않으므로 비용이 0이고, 

파일의 길이가 2일 경우부터 4일 경우까지 비용을 확인해보아야 한다.

예를 들어 파일의 길이가 3일 경우는 파일을 합치는 방법을 

(1번) + (2번,3번)인 경우와 (1번, 2번) + (3번)인 경우로 나눌 수 있다.

이렇게 나눠보기 위해 기존의 두 파일을 합치는 비용이 미리 계산되어 있어야 한다.

누적합 S = [0, 40, 70, 100, 150]

 

 

길이가 2일 경우,

(1,2), (2,3), (3,4) 파일로 나눌 수 있는데,

1번부터 2번파일까지의 비용은 (1~1의 비용(0) + 2~2의 비용(0)) + (1~2까지 누적합(70)) = 70 이 되고,

2번부터 3번파일까지의 비용은 (2~2의 비용(0) + 3~3의 비용(0)) + (2~3까지 누적합(60)) = 60 이 되고,

3번부터 4번파일까지의 비용은 (3~3의 비용(0) + 4~4의 비용(0)) + (2~3까지 누적합(80)) = 80 이 된다.

여기서 DP[][]의 상태는 아래 그림과 같다.

 

 

다음 길이가 3일 경우,

(1 + 2,3), (1,2 + 3), (2, + 3,4), (2,3 + 4) 파일로 나눌 수 있는데

1번부터 3번파일까지의 비용은 min(1~1의 비용(0) + 2~3의 비용(60).

 1~2의 비용(70) + 3~3의 비용(0)) 

+ (1~3까지의 누적합(100)) = 160 이 된다.

2번부터 4번파일까지의 비용은 min(2~2의 비용(0) + 3~4의 비용(80).

 2~3의 비용(60) + 4~4의 비용(0)) 

+ (2~4까지의 누적합(110)) = 170 이 된다.

 

 

마지막으로 길이가 4일 경우,

(1 +,2,3,4), (1,2 + 3,4), (1,2,3 + 4) 파일로 나눌 수 있는데,

1번부터 4번파일까지의 비용은 min(1~1의 비용(0) + 2~4의 비용(170).

 1~2의 비용(70) + 3~4의 비용(80),

 1~3의 비용(160) + 4~4의 비용(0))

 + (1~4까지의 누적합(150)) = 300 이 된다.

 

여기서 마지막으로 1~4번까지의 파일을 합쳐야 하므로

DP[1][N]을 출력해주면 된다.

 

여기서 찾을 수 있는 점화식은

DP[i][k] + DP[k+1][j] + sum(A[i]~A[j]) 가 될 것이다.

(i~k)까지 비용의 합과 그 다음 (k+1지점부터 마지막 지점)까지의 합의 최소에

(i~j)까지의 누적합을 더해주면 얻고자하는 해를 얻을 수 있다.

 

여기서 DP[][]는 i부터 j까지 파일을 합치는데 드는 비용으로 정의하고 푸는 것이 중요한 포인트인것 같다.

 

 

출처: https://data-make.tistory.com/402 [Data Makes Our Future:티스토리]