[백준 11066] 파일 합치기 (C#, C++) - soo:bak

문제 링크

11066번 - 파일 합치기

설명

K개의 파일이 연속으로 주어지는 상황에서, K (3 ≤ K ≤ 500)와 각 파일의 크기가 주어질 때, 모든 파일을 하나로 합치는 최소 비용을 구하는 문제입니다.

두 파일을 합칠 때의 비용은 두 파일 크기의 합이며, 파일의 순서는 바꿀 수 없습니다. 어떤 순서로 합치느냐에 따라 총 비용이 달라집니다.

접근법

구간 DP로 최적 분할 지점을 찾습니다.

먼저 dp[l][r]을 구간 [l, r]의 파일을 합치는 최소 비용으로 정의합니다. 길이 1인 구간은 비용이 0입니다.

누적합을 미리 계산하면 구간 합을 O(1)에 구할 수 있습니다.

다음으로, 구간 [l, r]을 두 부분으로 나누는 지점 k를 l부터 r-1까지 시도합니다. 각 k에 대해 dp[l][k] + dp[k+1][r] + (구간 [l, r]의 크기 합)을 계산하여 최솟값을 선택합니다.

이렇게 구간 길이를 1부터 늘려가며 모든 dp 값을 채웁니다.

예를 들어 파일 크기가 [40, 30, 30, 50]일 때, (40+30) + (70+30) + (100+50) = 320으로 합칠 수도 있고, (30+30) + (40+60) + (100+50) = 280으로 합칠 수도 있습니다. DP로 모든 가능한 분할을 비교하여 최소 비용을 찾습니다.

시간 복잡도는 O(K³)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var t = int.Parse(Console.ReadLine()!);
      while (t-- > 0) {
        var k = int.Parse(Console.ReadLine()!);
        var parts = Console.ReadLine()!.Split();

        var size = new int[k + 1];
        var prefix = new int[k + 1];
        for (var i = 1; i <= k; i++) {
          size[i] = int.Parse(parts[i - 1]);
          prefix[i] = prefix[i - 1] + size[i];
        }

        const int INF = int.MaxValue;
        var dp = new int[k + 2, k + 2];

        for (var len = 1; len < k; len++) {
          for (var l = 1; l + len <= k; l++) {
            var r = l + len;
            var best = INF;
            var rangeSum = prefix[r] - prefix[l - 1];

            for (var mid = l; mid < r; mid++) {
              var cand = dp[l, mid] + dp[mid + 1, r] + rangeSum;
              if (cand < best)
                best = cand;
            }
            dp[l, r] = best;
          }
        }

        Console.WriteLine(dp[1, k]);
      }
    }
  }
}

C++

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

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tc; cin >> tc;
  while (tc--) {
    int k; cin >> k;
    vi size(k + 1), prefix(k + 1, 0);
    for (int i = 1; i <= k; i++) {
      cin >> size[i];
      prefix[i] = prefix[i - 1] + size[i];
    }

    const int INF = INT_MAX;
    vvi dp(k + 2, vi(k + 2, 0));

    for (int len = 1; len < k; len++) {
      for (int l = 1; l + len <= k; l++) {
        int r = l + len;
        int best = INF;
        int sum = prefix[r] - prefix[l - 1];

        for (int mid = l; mid < r; mid++) {
          int cand = dp[l][mid] + dp[mid + 1][r] + sum;
          if (cand < best)
            best = cand;
        }
        dp[l][r] = best;
      }
    }

    cout << dp[1][k] << "\n";
  }

  return 0;
}