[백준] 11066_파일 합치기 :: Python

문제

🔗 [백준] 11066_파일 합치기

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

⭐️ 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 
⭐️ 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

---

아이디어

풀이 방법이 잘 떠오르지 않아서 다른 분들의 블로그를 참고했다. (참고 사이트 부분에 기재)

1. 먼저, 최종 파일을 만드는 데 드는 비용의 합을 문제에서는 어떻게 구하고 있는지 살펴보자.

   예시

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

   • 어떤 파일 X(i~j)가 X(i~m), X(m+1~j)라는 파일을 합침으로서 만들어진다면
     X(i~j) = X(i~m)를 만드는 데 든 비용 + X(m+1~j)를 만드는 데 든 비용 + (i~j까지의 파일의 크기)
   • 예시 위 정리처럼 X를 사용해 표기해보면

   X(1~4) = 310
   X(1~4) = X(1~3) + X(4) + C1 + C2 + C3 + C4
   	   = X(1~3) + 0(⭐️ 챕터 하나만 들어있는 파일은 만드는 비용이 없음 ⭐️) + 150
          = X(1) + X(2~3) + C1 + C2 + C3 + 150
          = 0 + X(2~3) + 250
          = X(2) + X(3) + C2 + C3 + 250
          = 0 + 0 + 60 + 250 
          = 310

2. 그렇다면, 파일을 합치는 데 드는 최소 비용은 어떻게 구할 수 있을까?

   • dp[i][j] 를 Ci부터 Cj까지의 파일을 합치는 최소비용이라고 하자.
   • dp[i][j] = min{dp[i][m] + dp[m+1][j] (for i <= m < j)} + (Ci~Cj까지 파일 크기의 합) 이라고 할 수 있다.
     • m에 대해 (i <= m < j) 범위로 순회해가며 최소값을 찾는다.
   • 유의할 점은 dp[x][x] 처럼, 하나의 파일을 나타내는 경우 파일을 합치는 최소 비용은 0이다!
     파일 하나는 만드는 비용이 들지 않는다.

---

풀이

• 구현 시 유의할 점

  • 2차원 배열을 사용해서 dp를 진행하는데, 순회 시 오른쪽 아래 대각선 ↘️ 방향으로 진행하며 값을 채워간다.

• 코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    K = int(input())
    chapters = [0] + list(map(int, input().split()))
    
    # cost[i] = chapter 1 ~ chapter i 까지 파일 크기의 누적합
    cost = [0] * (K + 1)
    for i in range(K + 1):
        if i == 0:
            continue
        cost[i] = cost[i-1] + chapters[i]
    
    # dp[i][j] = chapter i ~ chapter j 까지 파일을 합칠 때 최소 비용
    # dp[i][j] = for i <= k < j, 
    #            min(dp[i][k] + dp[k+1][j]) + cost[j] - cost[i-1]
    
    # ↘️ 대각선 방향으로 순회한다
    dp = [[0] * (K + 1) for _ in range(K + 1)]
    for x in range(K):
        for i in range(1, K+1):
            j = i + x
            if j >= K + 1:
                break
            
            # 자기 자신을 합치는 비용은 0이다.
            if i == j:
                continue

            # 연속된 두 챕터를 합치는 비용
            if j == i + 1:
                dp[i][j] = chapters[i] + chapters[j]
                continue
            
            memo = []
            for m in range(i, j):
                memo.append(dp[i][m] + dp[m+1][j])
            dp[i][j] = min(memo) + cost[j] - cost[i-1]

    print(dp[1][K])

---

참고 사이트

• mumu 개발 블로그 - [다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기