백준 11066 파일 합치기

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

int testcase;
int fileSize[501];
int sum[501];
int dp[501][501];
const int intmax = 2100000000;

void initData() {
	for (int i = 0; i < 501; i++) {
		fileSize[i] = 0;
		sum[i] = 0;
		for (int j = 0; j < 501; j++) {
			dp[i][j] = 0;
		}
	}
	return;
}

int solve(int i, int j) {
	if (i == j) return 0;
	int minResult = intmax;
	for (int k = 0; k < abs(i - j); k++) {
		minResult = min(minResult, dp[i][i + k] + dp[i + k + 1][j] + sum[j] - sum[i - 1]);
	}
	return minResult;
}

int main() {
	cin >> testcase;
	while (testcase > 0) {
		testcase--;
		initData();
		int fileNum;
		cin >> fileNum;

		for (int i = 1; i <= fileNum; i++) {
			cin >> fileSize[i];
			sum[i] = sum[i - 1] + fileSize[i];
		}

		for (int i = 0; i <= fileNum; i++) {
			for (int j = 1; i + j <= fileNum; j++) {
				dp[j][i + j] = solve(j, i + j);
			}
		}
		cout << dp[1][fileNum] << endl;
	}
	return 0;
}

한방에 맞췄다!

처음에 인접한 파일끼리만 합칠수 있다는 걸 모르고 있을 때는, 

아니 이게 시간복잡도가 N^N인거 같은데 도대체 어떻게 풀리는거지;;

라는 생각을 하면서 고민하다 잘 안풀려서 '질문' 탭을 눌렸다

그런데 거기서 '소설'이니까 인접한 파일끼리만 합칠 수 있다는 걸 봤다. (문제를 제대로 읽어야 한다..)

그걸 보는순간

그럼 배열을 양분하고 각 양분된 배열을 합치는 시간의 합이 전체 배열을 합치는 시간이구나!

라는 생각이 들었다.

DP[i][j]는 '배열의 [i...j]의 파일을 합치는 최소 시간'이다.

DP[i][j] = min(

 DP[i][i+k] + DP[i+k+1][j]

(k := 0...j-1)

)

이라는 결론에 도달해서 문제를 풀었는데

예제에서 오답이 나왔다.

고민고민해보니 내가 푼건 파일을 합치는 '누적'이 아니였다.

파일을 합치는 누적된 시간을 넣으려면 각 DP[i][j]에 sum(i..j)를 넣어야 된다. 

그런데 가만 생각 해보니 여기서 sum(i..j)는 부분 합이다.

따라서 sum(i..j)는 sum(0..j) - sum(0..i-1)이므로 위의 소스처럼 작성했다.

결론은

DP[i][j] = min(

 DP[i][i+k] + DP[i+k+1][j] + sum(0..j) - sum(0..i-1)

(k := 0...j-1)

)

이다.

solve 함수에서 부분합을 가장 마지막에 더했으면 조금 더 최적화가 됐을듯.

'다이나믹 프로그래밍이란 부분문제와 중복된 문제가 핵심' 이란걸 기억하면 문제를 푸는 아이디어를 떠올릴 수 있을것 같다.