[Python] 백준 11066번 - 파일 합치기 (골드 3)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - DP

 

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

 

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

 

---

 

2024.04.09 - [Algorithm/백준] - [Python] 백준 11049번 - 행렬 곱셈 순서 (골드 3)

[Python] 백준 11049번 - 행렬 곱셈 순서 (골드 3)

 

앞서 풀었던 문제와 유사한 문제이다.

 

2차원 DP테이블을 이용하여 상관관계를 구해 풀어내는 문제다.

 

이번에도 역시나 점화식을 구하는데 어려움이 있었으나 한 블로그의 도움을 받아 실마리를 잡아 풀 수 있었다.

 

 

참고한 블로그

https://supersfel.tistory.com/entry/11066%ED%8C%8C%EC%9D%BC-%ED%95%A9%EC%B9%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%84%A4%EB%AA%85%EC%9C%84%EC%A3%BC

11066_파일 합치기 ( 파이썬, 설명위주 )

 

 

---

 

문제 풀이 방법은 앞선 문제와 비슷하다. 주의할 점은 인접한 값끼리만 합치며 합친것의 합을 다시 합하여 DP테이블에 적용해야 한다는 것이다.

 

예제로 알아보자.

1
4
40 30 30 50

 

전제조건이 하나 있다.

바로 누적합을 이용한다는 것이다.

리스트 하나를 선언하여 [0, 40, 70, 100, 150] 을 구해 놓는다.

위 누적합 리스트는 dp테이블을 구하는데 사용된다.

 

1. 간격이 1인 묶음

[40, 30] [30, 30], [30, 50] 총 세 묶음이 나온다.

 

	0	1	2	3	4
0
1			70
2				60
3					80
4

 

dp[1][2] = 1번부터 2번까지 파일의 합

dp[2][3] = 2번부터 3번까지 파일의 합

dp[3][4] = 3번부터 4번까지 파일의 합

 

위와 같이 정리할 수 있다.

 

2. 간격이 2인 묶음

 

이제부터가 진짜다.

 

dp[1][3] = 1번부터 3번까지 파일의 합을 나타낸다.

이를 구하기 위해선 총 2가지 방법이 요구된다.

1+(2+3)과 (1+2)+3을 구해서 작은 값을 dp에 넣어야한다.

 

마찬가지로 dp[2][4] = min(2+(3+4), (2+3)+4)

 

우린 참고로 (1+2), (2+3), (3+4)의 값을 이미 알고 있다.

 

	0	1	2	3	4
0
1			70
2				60
3					80
4

 

dp[1][2] = (1+2)

dp[2][3] = (2+3)

dp[3][4] = (3+4)

 

그럼 여기서 생각을 조금 더 해보면 dp[1][3]과 dp[2][4]를 구할 수 있다.

 

dp[1][3]

1+(2+3) -> 0 + 60 + 100(1~3누적합) = 160

(1+2)+3 -> 70 + 0 + 100(1~3 누적합) = 170

 

dp[2][4]

2+(3+4) -> 0 + 80 + 110 (2~4 누적합 = 150-40) = 190

(2+3)+4 -> 60 + 0 + 110 (2~4 누적합) = 170

 

위에서 0이 무엇이냐면

 

각각 1개는 합이 아닌 개별이다. 그렇기 때문에 0으로 계산한다.

 

	0	1	2	3	4
0
1			70	160
2				60	170
3					80
4

 

 

3. 간격이 3인 묵음

dp[1][4] = 1번부터 4번까지 파일의 합

1+(2+3+4) = 0 + dp[2][4] + 150 (1~4 누적합) = 170 + 150 = 320

(1+2)+(3+4) = dp[1][2] + dp[3][4] + 150 = 70 + 80 + 150 = 300

(1+2+3)+4 = dp[1][3] + 0 + 150 = 160 + 150 = 310

 

우리는 300이라는 최소값을 얻을 수 잇다.

 

이를 알아보기 쉽게 코드형식으로 구현하자면

 

간격 1

dp[1][2] = dp[1][1] + dp[2][2] + sum_list[2]-sum_list[0]

dp[2][3] = dp[2][2] + dp[3][3] + sum_list[3] - sum_list[1]

dp[3][4] = dp[3][3] + dp[4][4] + sum_list[4] - sum_list[2]

 

간격 2

dp[1][3]

1+(2+3) = dp[1][1] + dp[2][3] + sum_list[3] - sum_list[0]

(1+2)+3 = dp[1][2] + dp[3][3] + sum_list[3] - sum_list[0]

 

dp[2][4]

2+(3+4) = dp[2][2] + dp[3][4] + sum_list[4] - sum_list[1]

(2+3)+4 = dp[2][3] + dp[4][4] + sum_list[4] - sum_list[1]

 

간격3

1+(2+3+4) = dp[1][1] + dp[2][4] + sum_list[4] - sum_list[0]

(1+2)+(3+4) = dp[1][2] + dp[3][4] + sum_list[4] - sum_list[0]

(1+2+3)+4 = dp[1][3] + dp[4][4] + sum_list[4] - sum_list[0]

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    K = int(input()) # 3 <= K <= 500
    data = [0]
    data += list(map(int, input().split()))
    
    dp = [[0 for _ in range(K+1)] for _ in range(K+1)]
    
    sum_list = [0]
    for i in range(1, K+1):
        sum_list.append(sum(data[1:i+1]))
    
    for step in range(1, K):
        for start in range(1, K):
            if start + step > K:
                break
            dp[start][start+step] = int(1e9)
            
            for t in range(step):
                dp[start][start+step] = min(dp[start][start+step],
                                            dp[start][start+t]+dp[start+t+1][start+step]+sum_list[start+step]-sum_list[start-1])
    print(dp[1][K])