포스트

(백준/C++) 11066_파일 합치기

11066번: 파일 합치기 (acmicpc.net) 문제는 여러 개의 파일을 하나로 합치는 과정에서 발생하는 비용을 최소화하는 문제입니다. 각 파일은 다른 크기를 가지고 있으며, 두 파일을 합칠 때 그 크기의 합만큼의 비용이 발생합니다.

이 문제를 동적 계획법으로 접근하면, 각 부분 문제의 최적 해를 찾아 전체 문제의 최적 해를 구할 수 있습니다.

동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.


접근 방법

기본적인 문제의 접근 방법은 다음과 같습니다.

  1. 파일을 합치는 경우는 앞쪽 파일 2개, 뒤쪽 파일 2개, 이후 이 두 파일을 합치는 식으로 서로 다른 부분을 먼저 합친 후 합쳐진 파일들을 서로 합치는 식으로 풀어갈 수 있습니다.
  2. 파일을 합치는 시간은 서로의 파일을 합친 후 그 크기의 합만큼 시간이 걸립니다.

1) Tabulation(Bottom-up) 방식

이 문제는 2개의 서로 다른 파일들을 합친 값이 더 적은 비용을 찾아야 하므로 작은 문제(2개의 파일을 합치는 것)부터 해를 찾고, 작은 것부터 차례대로 해결해 나가다 보면 최종 해를 찾을 수 있습니다.

최적 부분 구조

  • 이 문제에서의 전체 문제는 여러 개의 파일을 하나로 합치는 것입니다.
  • 이를 부분 문제로 나누면 특정 구간 i부터 j까지의 파일을 합치는 최소 비용을 구하는 문제가 될 수 있습니다.
  • 예를 들어, [40, 30, 30, 50]의 최소 비용을 구하는 방법으로는, [40, 30]을 합치는 비용과 [30, 50]을 합치는 비용을 구하고, [[40, 30], [30, 50]]을 합치는 비용을 구해 계산할 수 있습니다.

중복된 부분 문제

  • 따라서 이 문제의 중복된 부분 문제로는 [A, B, C, D, E]를 합칠 때, [A, B]를 먼저 구하고 [[A, B], C]를 구하는 식으로 부분 문제가 발생할 수 있습니다.

2) 점화식 찾기

따라서 점화식은 다음과 같이 정의될 수 있습니다.

\[dp[i][j]=\min_{ { i\le m<j } }(dp[i][m]+dp[m+1][j]+sum(i,j))\]

여기서 $sum(i,j)$는 i번째부터 j번째까지의 파일 크기의 합입니다. 이는 두 파일을 합치는 비용을 나타냅니다.


풀이

이 코드에서

  • dp[i][j]는 i번째부터 j번째까지의 파일을 합칠 때의 최소 비용을 저장하고,
  • sumy[i]는 0번째부터 i번째까지의 파일 크기의 합을 저장한 부분 합입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAX = 2000000000;

void solve(int K, vector<int>& sumy, vector<vector<int>>& dp)
{
	// 길이가 2개인 부분 문제부터 차근차근 해결한다.
	for (int len = 2; len <= K; len++)
	{
		for (int i = 0; i <= K - len; i++)
		{
			int j = i + len - 1;

			// 부분 문제를 위해 중간 크기인 m을 잡아야 한다.
			for (int m = i; m < j; m++)
			{
				int cost = dp[i][m] + dp[m + 1][j] + sumy[j] - (i > 0 ? sumy[i - 1] : 0);
				dp[i][j] = min(dp[i][j], cost);
			}
		}
	}
}

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

	int T;
	cin >> T;
	while(T--)
	{
		int K;
		cin >> K;

		vector<int> sizes(K);
		vector<int> sumy(K);
		vector<vector<int>> dp(K, vector<int>(K, MAX));

		for(int i = 0; i < K; i++)
		{
			cin >> sizes[i];
			sumy[i] = sizes[i] + (i > 0 ? sumy[i - 1] : 0);
			dp[i][i] = 0;
		}

		solve(K, sumy, dp);
		cout << dp[0][K - 1] << '\n';
	}
}
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.