백준 11066: 파일 합치기

문제 요약

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

문제 분류

• 다이나믹 프로그래밍
• 누적 합

문제 풀이

백준에서는 명시되어있지 않지만, 풀이 법에 누적 합의 아이디어를 사용하였기 때문에 분류에 추가하였다.

기본적으로는 DP인데, 2차원 배열을 사용하였다. dp[s][e]는 s~e까지의 파일을 합친 최소의 누적 비용이다. 먼저,s + 1 == e인 경우에는 연속된 두 개의 파일을 합치는 경우이므로 ary[s] + ary[e]를 반환하면 된다.s == e일 경우는 1개의 파일을 합치는 경우인데, 이때는 아무런 파일도 합치지 않으므로 0을 반환한다.

이제 다음이 중요한데, s~e범위에서 가운데를 짤라서 dp점화식을 세운다. 무슨 말이냐면, s <= i < e에 대해, dp[s][e]는 sol(s, i) + sol(i + 1, e)의 최솟값이 된다.
즉, 점화식은 dp[s][e] = min(dp[s][e], sol(s, i) + sol(i + 1, e));이 된다.

그 다음에 자기 자신의 비용도 포함하여야 하기 때문에 누적을 시켜줘야 하는데, 여기서 누적 합을 사용한다. dp[s][e] += S[e] - S[s - 1];로써 s~e의 누적 합을 합산해주고 반환한다. 당연히 여기서 S[]는 ary[]에 대한 누적 합이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int ary[501], dp[501][501], n, S[501];

int sol(int s, int e)
{
	if (dp[s][e]) return dp[s][e];
	if (s == e) return 0;
	if (s + 1 == e) return ary[s] + ary[e];
	for (int i = s; i < e; i++) {
		if (!dp[s][e])
			dp[s][e] = sol(s, i) + sol(i + 1, e);
		dp[s][e] = min(dp[s][e], sol(s, i) + sol(i + 1, e));
	}
	dp[s][e] += S[e] - S[s - 1];
	return dp[s][e];
}

int main()
{
	int t;
	cin >> t;
	while (t--) {
		memset(dp, 0, sizeof(dp));
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", ary + i);
			S[i] = S[i - 1] + ary[i];
		}
		printf("%d\n", sol(1, n));
	}

	return 0;
}