(백준/C++) 11066_파일 합치기
11066번: 파일 합치기 (acmicpc.net) 문제는 여러 개의 파일을 하나로 합치는 과정에서 발생하는 비용을 최소화하는 문제입니다. 각 파일은 다른 크기를 가지고 있으며, 두 파일을 합칠 때 그 크기의 합만큼의 비용이 발생합니다.
이 문제를 동적 계획법으로 접근하면, 각 부분 문제의 최적 해를 찾아 전체 문제의 최적 해를 구할 수 있습니다.
동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.
접근 방법
기본적인 문제의 접근 방법은 다음과 같습니다.
- 파일을 합치는 경우는 앞쪽 파일 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 라이센스를 따릅니다.