백준 알고리즘 23단계 동적 계획법 2- 파일 합치기(11066번) Python

이번에 풀어볼 문제는 백준 알고리즘의 파일 합치기 문제이다.

해당 문제에 대한 링크는 아래와 같다.

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

11066번: 파일 합치기

 

1. 문제 확인

 

2. 문제 풀이

dp[0][m-1]+dp[m][m]

import sys
 
n=int(input())
 
while n>0:
    n-=1
    K=int(input())
    file_list=list(map(int,sys.stdin.readline().split()))
    dp=[[0 for _ in range(K)] for _ in range(K)]
    sum=[0]*(K+1)
    sum[0]=0
    sum[1]=file_list[0]
    for i in range(1,K+1):
        sum[i]=sum[i-1]+file_list[i-1]
 
    for x in range(1,K+1):
        for i in range(K-x):
            j=i+x
            dp[i][j]=999999999999
            for k in range(i,j):
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i])
 
 
    print(dp[0][K-1])