[DP] 백준 11066 파일 합치기

Halo·2025년 4월 15일

Algorithm

목록 보기

13/85

🔍 Problem

일단 dp를 사용해야한다. 왜냐하면 각 파일을 합치는 과정에서 상향식으로 접근하고 전에 저장해놓은 값들을 사용하기 때문이다. 가장 신경써야할 것은 만약 i,j까지 있다면 예시에서는 1~4 (40,30,30,50) 1~4가의 합이 최소가 되기 위해서는 i~m부터 m+1~j의 합도 최소가 되어야한다. 이것을 고려하기 위해 dp 매트릭스를 만들어 i~j까지의 최소 비용을 저장해놓는다. 하지만 이것을 하기전에 누적합을 계산하여 dp[i][j]애 저장해놓고 최소비용을 계산하기 용이하게 만든다.

📒 해결과정

가. i~j까지 누적합 계산

누적합을 계산하는 이유는 `dp[i][j] = i~j의 누적합 + min([dp[i][m]+dp[m+1][j] for m in range(i,j)])` 을 계산하기 위해서이다. 여기서 첫번째 i~j의 누적합은 `(30,40),50` (30과 40을 먼저 묶고, 50을 나중에 묶는다는 의미 ) 을 계산할 때 이 값의 비용은 `30~50의 누적합 + 30,40의 합비용 + 50의 합비용`이기 때문이다. 이것은 앞의 식이 30과 40을 먼저 묶는다는것이 최소비용이기 때문에 이렇게 세운것이고 이에따라 뒤에 `min`도 설명될 수 있다. 최소값이란 것이다. 다시 한번 말하지만 30과 40의 묶임이 최소비용을 의미하기 때문에 min 에서 이것이 나온것이고 이것과 30~50의 누적합+50의 최소비용 = 0 이 곧 30~50의 최소비용이 되는 것이다.

나. 최소비용 계산

참고로 필자는 매트릭스를 직접그려보며 규칙을 찾는게 이 문제를 이해하는데 도움이 많이 되었다. 독자도 한번 그려보면 왜 dp를 매트릭스로 만들고 이전값을 사용하여 어떻게 dp 매트릭스를채워나간 다는 것인지 이해가 될 것이다.

💻 Code

import sys

cnt=int(sys.stdin.readline())

def solve(list_):
    N=len(list_)
    dp=[[0]*N for _ in range(N)]

    def return_sum(i,j):
        sum=0
        for n in range(i,j+1):
            sum+=list_[n]
        return sum

    # 1. 누적합 삽입 , 누적합 = 초기 dp[i][j]
    for i in range(0,N-1):
        for j in range(i+1,N):
            dp[i][j] = return_sum(i,j)

    # 3. dp 매트릭스 채우기
    for k in range(0,N-1):
        for i in range(0,N-k-1):
            j=i+k+1
            dp[i][j]+=min([dp[i][m]+dp[m+1][j] for m in range(i,j)])
                

    return dp[0][N-1]

for _ in range(cnt):
    size=int(sys.stdin.readline())
    list_=list(map(int, sys.stdin.readline().split()))
    print(solve(list_))