[C++] 백준/Gold/11066. 파일 합치기

 

파일 합치기 (백준 11066번)

문제 개요

여러 파일을 하나의 파일로 합칠 때, 두 파일을 합치는 비용은 두 파일의 크기의 합이다.
여러 개의 파일을 주어진 순서대로 합칠 때,
전체 합치는 비용을 최소화하는 합치는 순서를 찾는 문제이다.

접근 방법: 동적 계획법 (DP)

문제는 구간 DP 문제의 대표적인 예제로,
파일 $ A_i $의 크기를 배열 $ \text{arr}[i] $로 두면,
구간 $[i, j]$에 있는 파일들을 합치는 최소 비용 $ dp[i][j] $는 다음 점화식으로 구할 수 있다.

1. 누적 합 (Prefix Sum)

연속된 파일 크기의 합을 빠르게 계산하기 위해,
누적 합 배열 $ \text{subtotal} $을 사용한다.
$$
\text{subtotal}[k] = \sum_{l=0}^{k-1} \text{arr}[l]
$$
따라서, 구간 $[i,j]$의 파일 크기 합은 다음과 같다.
$$
\text{sum}(i,j) = \text{subtotal}[j+1] - \text{subtotal}[i]
$$

2. 동적 계획법 점화식

구간 $[i,j]$의 파일들을 합치는 최소 비용 $ dp[i][j] $는 다음과 같이 정의한다.

• 기저 조건:
  단일 파일인 경우, 비용은 0
  $$
  dp[i][i] = 0 \quad \text{for all } i
  $$
• 점화식:
  구간 $[i,j]$를 합칠 때, 중간 분할점 $ k $ $(i \le k < j)$를 기준으로
  양쪽 구간의 합치는 최소 비용과, 두 구간을 합칠 때의 비용(두 구간의 크기의 합)을 더한 값 중 최소값으로 결정된다.
  $$
  dp[i][j] = \min_{i \le k < j} \left{ dp[i][k] + dp[k+1][j] + \text{sum}(i,j) \right}
  $$
  여기서 $\text{sum}(i,j) = \text{subtotal}[j+1] - \text{subtotal}[i]$이다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        vector<int> arr(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }

        // 누적 합 배열: subtotal[i] = arr[0] + arr[1] + ... + arr[i-1]
        vector<int> subtotal(n + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
            subtotal[i] = subtotal[i - 1] + arr[i - 1];
        }

        // dp[i][j] : 구간 [i, j]의 파일들을 합치는 최소 비용.
        // 초기값: 같은 위치는 파일 하나이므로 비용 0.
        vector<vector<int>> dp(n, vector<int>(n, 1e9));
        for (int i = 0; i < n; ++i)
        {
            dp[i][i] = 0;
        }

        // 길이가 2부터 n인 구간에 대해 비용 계산
        for (int len = 2; len <= n; ++len)
        {
            for (int start = 0; start <= n - len; ++start)
            {
                int end = start + len - 1;
                // 중간 분할점 mid를 통해, 두 부분 구간을 합치는 경우를 고려
                for (int mid = start; mid < end; ++mid)
                {
                    dp[start][end] = min(dp[start][end],
                        dp[start][mid] + dp[mid + 1][end] + (subtotal[end + 1] - subtotal[start]));
                }
            }
        }

        cout << dp[0][n - 1] << '\n';
    }
}