[백준 11066][파이썬] 파일 합치기 (dp 알고리즘)

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

11066번: 파일 합치기

dp를 활용하여 삼중 반복문을 사용하여 푸는 문제이다.

 

dp[x][y]는 다음과 같이 정의한다.

 

인덱스 x 파일부터 인덱스 y 파일까지 하나의 파일로 합치는데 필요한 최소비용

 

이를 이용하여 dp 알고리즘을 적용하면 된다.

 

가장 먼저 x와 y가 동일한 경우를 보자.

 

다음과 같이 파일들의 크기를 나열할 때

15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

dp[0][0], dp[1][1] ... 과 같이 x와 y의 값이 동일하다면 하나의 파일을 의미하고 이미 하나의 파일이기 때문에 합칠 필요가 없다.

 

그렇기에 x와 y가 같은 위치의 값은 모두 0이다.

 

    for i in range(n):
        dp[i][i] = 0 #길이가 1인 것의 최소 비용

이 다음부터 dp 알고리즘을 적용하는데 상당히 까다롭다.

 

위처럼 15가지의 파일의 크기가 나열되어있을 때 언뜻 살펴보더라도 무수히 많은 경우의 수가 보인다.

 

다행히도 파일들의 개수는 500을 넘지 않는다.

 

문제의 제한 시간은 2초, 파이썬에서 1억번의 연산을 할 때 1초가 걸리는 것을 감안하면 O(N^3)까지는 시간 초과가 발생하지 않는다.

 

현재까지 길이가 1인 경우는 모두 구한 상황이다.

 

이제부터는 길이가 2인 경우, 3인 경우.. n인 경우까지 모두 구할 차례이다.

 

길이가 2인 경우를 생각해보면 두 개의 숫자가 합쳐지는 1가지 경우밖에 존재하지 않는다.

 

즉 dp[x][x+1]의 경우 둘을 더하면 된다.

 

길이가 3인 경우 다음과 같이 2가지 경우가 존재한다.

문제에서 주어진 길이는 15. 우리는 길이가 2, 3인 모든 범위에 대하여 최소 비용을 구한다.

 

이제 길이가 15인 경우를 생각해보면서 공통적으로 적용할 알고리즘을 생각해야한다.

 

우리는 길이를 증가시켜가면서 최소 비용을 구해왔기 때문에 길이가 10인 경우를 구할 때는 모든 범위에 대해서 길이가 1~14인 최소 비용을 알고있다.

 

즉 다음과 같이 반복을 하면 된다.

dp[1][1]값과 dp[2][15]의 합을 구하고 dp[1][2]값과 dp[3][15] 합을 구하고... 이러한 과정을 반복해서 가장 작은 값을 구하면 된다.

 

그런데 dp[1][1] + dp[2][15]의 값은 한 페이지를 만들 때의 최솟값이 아닌 두 페이지를 만들 때의 최솟값이다.

 

그리고 두 페이지를 합칠 때의 비용은 1에서 15까지의 모든 비용의 합을 더한 값이다.

 

즉 정확히는 dp[1][1] + dp[2][15] + sum(arr[1] ~ arr[15]) 이렇게 해당 범위의 모든 값을 더해주는 과정이 필요하다.

 

<최종 코드>

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int, input().split()))
    subtotal = [0]*(n+1)
    subtotal[0]=0
    for i in range(1, n+1): #누저합 구하기
        subtotal[i]=arr[i-1]
        subtotal[i]+=subtotal[i-1]
    dp=[ 
        [1e9]*n
        for _ in range(n)
    ]
    for i in range(n):
        dp[i][i] = 0 #길이가 1인 것의 최소 비용
    
    for i in range(2, n+1): #길이
        for j in range(n-i+1): #시작 인덱스
            for k in range(j, j+i-1): #하나한씩 돌음
                dp[j][j+i-1] = min(dp[j][j+i-1], dp[j][k]+dp[k+1][j+i-1]+subtotal[j+i]-subtotal[j]) 
    
    print(dp[0][n-1])