[DP] Python - 110066번, 파일 합치기

import sys
input = sys.stdin.readline

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

    sums = [0]*(K+1)
    for i in range(1, K+1):
        sums[i] = sums[i-1]+nums[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):  # 시작지점..K-1~0
            dp[j][j+i-1] = min([dp[j][j+k]+dp[j+k+1][j+i-1]
                                for k in range(i-1)]) + (sums[j+i-1]-sums[j-1])
    print(dp[1][K])

 

일단 sums는 무시한 채로 dp부터 설명한다.

dp[i][j]의 의미는 i~j까지의 최소합을 뜻한다. 즉, 예제에서 구하려는 값은 dp[1][4]이다.

dp는 이 상태로 초기화된다.

우선 길이가 2인 것들부터 채워나간다. 여긴 고민할 것 없이 두 수만 더하면 된다.

길이가 3일 때이다.

dp[1][3]의 경우를 생각해본다. 우리는 이 값이, (30+30)+(30+30+40)=160이란 것을 알고 있다.

우선, dp[1][1]+dp[2][3], dp[1][2]+dp[3][3]에서 최솟값을 찾는다. 그것은 전자로 60이다.(0+60)

그 다음은 여기에 1~3 범위 내의 모든 값의 합을 더해주는 것이다.

이 때, 합을 구하기 위해서 처음에 언급했던 sums를 이용한다.

즉, 60+(30+30+40) = 160이다.

이번엔 마지막으로 길이가 4일 때이며, 방금 전과 같이 진행한다.

dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4] 중 최솟값은 두번째 경우인 150이다.

여기에 1~4 범위의 합을 더하면, 150+150으로 300이 나온다.

 

여담으로, DP 문제는 이미 풀어봤던 문제를 다시 접하는 게 아니라면 DP에 무엇을 저장해야할지, 배열은 몇 차원이어야 하는지가 너무나도 생각이 나지 않는 것 같다.