[파이썬] [DP] 백준 11066 파일 합치기

문제

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

11066번: 파일 합치기

 

코드

import sys
INF=sys.maxsize

t=int(input())

while(t):
    t-=1
    k=int(input())
    arr=list(map(int, input().split()))

    dp=[[0]*k for _ in range(k)]

    subsum={-1:0}
    for i,v in enumerate(arr):
        subsum[i]=subsum[i-1]+v

    for i in range(1,k):
        for j in range(k-i):
        	//간격이 1일때
            if i==1:
                dp[j][j+1]=arr[j]+arr[j+1]
                continue
            dp[j][j+i]=INF
            //q는 cut
            for q in range(j,j+i):
                dp[j][j+i]=min(dp[j][j+i], dp[j][q]+dp[q+1][j+i]+subsum[j+i]-subsum[j-1])

    print(dp[0][k-1])

생각 정리

어떤 구간의 최소비용 minCost는, cut을 기준으로 분할할 때, 좌측 그룹의 최소 비용 + 우측 그룹의 최소 비용 + 좌측 압축 수와 우측 압축 수 더하기

이 때 좌측 압축 수 + 우측 압축 수는 그 구간의 모든 수의 합과 같음

 

 

https://developerbee.tistory.com/97

[알고리즘 / 백준] 11066 - 파일 합치기