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

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

[문제 요약]

- 소설가 김대전은 소서을 여러 장 나누어 쓴다. 각 장은 각각 다른 파일에 저장한다. 각 장이 쓰여진 파일을 합쳐서 한 개의 파일로 만든다. 

-

이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.- 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

 

[예시]

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

 

[문제 조건]

- 첫 줄에는 T가 입력으로 주어진다. ( T는 테스트 데이터의 개수)- 각 테스트 데이터는 두 개의 행으로 주어진다. 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K ( 3 ≤ K ≤ 500 ), 두 번째 행에는 1장 부터 K장까지 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.- 시간 제한 : 2초- 메모리 제한 : 256MB

 

[문제

 풀이]"이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다."미리 말하자면, 위에 빨간색으로 강조한 문장을 완벽히 이해한 상태에서 문제를 풀어야한다. 왜냐하면 필자는 저 문장의 존재를 모른채 문제를 풀었다가 2번의 삽질을 했기 때문이다.

 

필자가 처음에 생각했던 방법은 파일들 중 크기가 가장 작은 2개를 골라 합치고 합친파일+남은 파일 중에서도 다시 작은 파일 2개를 합쳐서 답을 구하는 방식을 진행했었는데 당연히 빨간색 문제 조건을 만족시키지 못하므로 틀린 풀이였다.

 

일단 저 빨간색 문장이 뭘 의미 하는지 생각해보자.

 

"소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고..." 이 구절이 핵심이다. 예를 들어 n번째 파일을 선택했다면 이 파일과 합치기 위해서는 n-1번째 파일이나 n+1번째 파일과 합쳐야되고, 이미 여러번 합쳐진 파일과 다른 단일파일 또는 합쳐진 파일과 합칠 때는 합쳤을때 파일 번호가 연속적이여야 한다는 것이다.

ex)

1	2	3	4	5
50	20	30	40	70

대충 이런식으로 파일이 있다고 할때 3번 파일은 2,4번파일과 합쳐야되고, 만약 (3,4) 파일을 합친 상태에서 다른 파일과 합치려면 2번파일과 5번파일 두개만 합칠 수 있다는 것이다. 또한 (1,2) 파일과 (4,5)파일이 있을때 두 파일은 합칠 수 없다.

 

여기까지 문제를 완전히 이해하는데 끝이 났다. 그러면 이제 코드를 어떤식으로 작성할것인가.

 

일단 파일이 n개가 있다고 가정해보자

그러면 합치는 방식은 위 그림과 같은 방식으로 1개짜리랑 N-1개 합쳤을때의 값, 2개짜리와 N-2개 합쳤을때의 값... 쭉 계산하면서 그 중 가장 작은 값이 정답이 될 것이다. 

 

N-1개 짜리 파일도 위와 같은 방식을 똑같이 적용하면 2번부터 N번째 파일까지 합쳤을 때의 최소비용이 나온다.

 

음? 큰 문제를 작은 문제로 쪼개서 푸는 방법이네?

 

그럼 다이나믹 프로그래밍(DP, Dynamic Programming) 방법을 쓸 수 있다는 것이다.

 

일단 dp테이블의 값을 dp[i][j] = i번째 번째 파일부터 j번째 파일까지 합칠때 최소비용 이라고 정의하자. 

dp[i][j]의 값을 구하는 방법은 위에서 언급한 방식으로 구하면되고, 이것을 표에 표시해서 나타내 보자

(파워포인트로 만들어서.....)

위 표를 예시로 했을 때 주어진 파일이 총 7개가 있다고 가정해보자.

dp[1][7]의 값은 표에 표시한 같은색 별끼리 합한 값 중 가장 작은 값을 dp[1][7]에 저장해주면 된다

.

필자는 dp테이블의 원소의 자료형을 pair<int,int>로 했다. 첫 번째 int는 문제에서 원하는 최소비용을 저장하면서 진행하고, 두번째 int는 최소비용일때의 파일의 크기를 의미한다.

그리고 i와 j가 같을 경우에는 (0,i번째 파일의 크기)로 미리 세팅해두 었고, i와 j가 1밖에 차이 나지 않는 경우는 어차피 2개의 파일밖에 합치는 경우가 없으므로 ( dt[i]+dt[j] , dt[i]+dt[j] ) 로 처음에 값을 저장해 두었고, 사실상 dp테이블 계산은 i와j가 2 차이날때부터 계산을 진행한다.

 

 

[소스코드]

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

int T;
using namespace std;

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

	cin >> T;

	while (T--)
	{
		vector<int> dt;
		vector<vector<pair<int, int>>> dp;
		int n;

		cin >> n;

		dt.resize(n + 1);
		dp.resize(n + 1);
		for (int i = 0; i <= n; i++) dp[i].resize(n + 1);

		for (int i = 1; i <= n; i++)
		{
			cin >> dt[i];
			dp[i][i].first = 0;
			dp[i][i].second = dt[i];
		}
		//파일 2개를 합치는 경우는 미리 저장
		for (int i = 1; i <= n - 1; i++)
		{
			dp[i][i + 1].first = dt[i] + dt[i + 1];
			dp[i][i + 1].second = dt[i] + dt[i + 1];
		}

		for (int i = 2; i <= n - 1; i++)
		{
			for (int j = 1; j + i <= n; j++)
			{
				dp[j][j + i].first = 999999999;
				dp[j][j + i].second = 999999999;
				for (int k = j; k + 1 <= j+i; k++)
				{
					pair<int, int> tmp1 = dp[j][k];
					pair<int, int> tmp2 = dp[k + 1][j+i];

					int card_sum = tmp1.second + tmp2.second;
					int total = card_sum + tmp1.first + tmp2.first;
                    //최소값 갱신
					if (dp[j][j + i].first > total)
					{
						dp[j][j + i].first = total;
						dp[j][j + i].second = card_sum;
					}
				}
			}
		}
		cout << dp[1][n].first << "\n";
	}
}

 

굳