[백준] 11066번 파일 합치기

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

11066번: 파일 합치기

정말 역대급 어려웠던 문제였다고 생각한다. 정답률은 50%가 넘는데 그거는 예제입력조차 정답이 나오지 않아서 사람들이 제출 시도 자체를 안 해서 그러는 것 같다. 솔직히 이 문제는 예제입력에서 정답이 나왔을 때 제출하면 거의 정답일 것 같다.

 

이 문제에서 주의할 것은 이 파일은 소설의 챕터이기 때문에 순서를 마음대로 바꾸면 안 된다. 무조건 입력으로 주어진 순서에서 인접한 파일끼리만 합칠 수 있다.

 

일단 코드부터 보자면

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n;
		cin >> n;
		vector<int> v(n + 1);
		vector<int> sum(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
			if (i == 0) {
				sum[i] = v[i];
			}
			else {
				sum[i] = sum[i - 1] + v[i];
			}
		}
		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
		for (int gap = 1; gap < n; gap++) {
			for (int start = 1; start + gap <= n; start++) {
				int end = start + gap;
				dp[start][end] = INT_MAX;
				for (int mid = start; mid < end; mid++) {
					if (dp[start][end] > dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1]) {
						dp[start][end] = dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start - 1];
					}
				}
			}
		}
		cout << dp[1][n] << '\n';
	}
	return 0;
}

테스트 케이스가 여러개라 돌리는 가장 바깥 for문을 제외하고 3중 for문이 핵심이다.

이차원 배열 dp[i][j]에는 i번째 챕터부터 j번째 챕터까지 합치는데에 드는 최소비용을 저장한다.

우리가 구하고자 하는 것은 "하나의 파일"로 합칠 때 필요한 최소비용이므로 dp[1][n]을 구하면 된다.

 

3중 for문 중 가장 바깥 for문은 gap을 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i와 j의 차이(간격)를 정해주는 for문이다.

만약 gap이 1이면 챕터 1과 2를 합친다던지 챕터 2와 3을 합치는 것과 같이 두 개의 연속된 챕터를 합치는 것이다.

gap이 2라면 챕터 1부터 챕터3까지 합친다던지 3개의 연속된 챕터를 합치는 것이다.

 

3중 for문 중 두 번째 for문(중간 for문)은 start를 1씩 늘려가면서 돌아가는데 dp[i][j]에서 i를 정해주는 for문이다.

즉, start는 "몇 번째 챕터부터" 더할지를 정하는 것이다.

gap이 3이고 start가 2라면 dp[2][2+3] 즉 dp[2][5]를 구하는 것이다.

따라서 end라는 변수를 만들어 start+gap을 end라는 변수에 저장해주었다. 윗줄 예시에서 end는 2+3=5이다.

 

제일 안쪽 for문은 mid를 1씩 늘려가면서 돌아간다. 파일을 합칠 때에는 두 개의 파일을 합쳐야 한다.

따라서 start~mid까지의 챕터와 mid+1~end 챕터를 더하게 될 텐데 그 두 부분으로 분리되는 부분이 바로 mid이다.

예를 들어 start가 1이고 gap이 4라서 dp[1][5]를 구해야 한다면 챕터1부터 챕터5까지를 합치는 최소 비용을 구하는 것인데

챕터1/챕터2~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 1)

챕터 1~2/챕터3~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 2)

챕터 1~3/챕터4~5 이렇게 두 부분을 합칠 수도 있고 (이 경우 mid는 3)

챕터 1~4/챕터5 이렇게 두 부분을 합칠 수도 있다. (이 경우 mid는 4)

mid의 역할이 바로 이렇다.

for문의 조건 부분이 mid <= end가 아니라 mid < end인 이유는 최소한 두 부분으로는 나눠져야 하기 때문이다.

만약 end와 mid가 같다면

챕터 1~5/없음 (mid가 5라면 즉, mid가 end와 같다면)

이렇게 챕터 1~5를 제외하면 나머지 부분은 없기 때문에 무조건 mid는 end보다 작아야 한다.

 

그리고 sum[i]에는 첫 번째 챕터부터 i번째 챕터까지의 합이 저장되어 있다.

따라서 sum[end] - sum[start - 1]은

(챕터1~챕터end까지의 합) - (챕터1~챕터 start-1까지의 합)이기 때문에

챕터start~챕터end까지의 합을 뜻한다.