[PS] 백준 11066번 파일 합치기

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

소설의 각 장(chapter)를 하나로 합치는데, 합치는 연산은 연속된 두 장을 하나로 합치는 연산이며 이 때의 비용은 각 장의 페이지 수이다. 총 장(chapter)의 수와 각 장의 페이지 수가 순서대로 주어졌을 때, 모든 장을 하나로 합치는데 필요한 최소 비용을 구하는 문제이다.

연속적인 장을 합친다라는 조건이 붙기 때문에, 각 단계마다 페이지 수가 가장 적은 장 두개를 합쳐가는 방법은 사용할 수 없다.

그렇다면 모든 경우를 구해봐야 한다.

그러면 n == 500일 때,
1단계에서 499가지
2단계에서 498가지
...
499단계에서 1가지
이므로 499! 의 시간복잡도가 나온다. (맞...나?)
따라서 안된다...

그러나 아래와 같은 사실을 이용해 memoization을 할 수 있다. 인덱스를 1부터 시작하도록 하자
1. dp[n][k]를 n번째 부터 k번째(n <= k) 장을 합치는 데 필요한 최소 비용이라고 한다면, 어떤 값 dp[n][k]는 어떤 상황에서도 변하지 않는다.
2. 그렇다면 dp[1][n]에 문제의 정답이 저장될 것이고, dp[1][n]을 구하기 위해서는 dp[1][n-1], dp[1][n-2], ... , dp[1][1]이 구해져야 한다. 즉, 더 작은 문제(length가 더 작다)의 해답이 더 큰 문제에 사용되며, 더 큰 문제에 사용될 때에도 값은 변하지 않는다.

그러면, 점화식을 구해보자.
files[i]: i번째 장의 페이지 수 라고 하면,
base case: dp[i][i] == files[i] 이고,
dp[n][m] = min(dp[n][m], dp[n][k] + dp[k + 1][m] + files[n] + files[n + 1] + ... + files[m]) 임을 알 수 있다. (n <= m, n <= k, k + 1 <= m)

위 식을 보면 dp[n][m]을 구하는데, 모든 경우를 검사하지만, dp[n][k] 나 dp[k + 1][m]은 dp[n][m]을 계산하기 전에, 이미 계산된 값을 재활용 하고 있음을 확인 할 수 있다. 그리고 이 dp[n][k]와 dp[k+1][m]은 dp[n][m]보다 작은 문제들이다. 따라서, 작은 문제들부터 구하고 memo해야 한다는 조건이 위 식에 추가되어야 하겠다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int t, n;
int files[500], dp[500][500], pre[500];

void solve() {
	for (int len = 2; len <= n; len++) {
		for (int left = 0; left < n - len + 1; left++) {
			int right = left + len - 1;
			dp[left][right] = INT32_MAX;

			for (int idx = 0; idx + left < right; idx++) {
				dp[left][right] = min(dp[left][right], dp[left][left + idx] + dp[left + idx + 1][right] + pre[right] - pre[left] + files[left]);
			}
		}
	}
}

void init() {
	pre[0] = files[0];
	for (int i = 1; i < n; i++) {
		pre[i] = pre[i - 1] + files[i];
	}
}

int main() {
	cin >> t;

	while (t--) {
		cin >> n;

		for (int i = 0; i < n; i++) {
			cin >> files[i];
		}

		init();
		solve();

		cout << dp[0][n - 1] << '\n';
	}
}