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

다이나믹 프로그래밍 문제입니다.

 

인접한 파일을 합쳐서 하나의 파일을 만들 때 최소 비용을 구하는 문제입니다.

 

for (int i = 2; i <= n; ++i) {
	for (int j = i - 1; j > 0; --j)	{
		DP[j][i] = 987654321;
		for (int k = j; k <= i; k++) {
			DP[j][i] = min(DP[j][i], DP[j][k] + DP[k + 1][i]);
		}
		DP[j][i] += sum[i] - sum[j - 1];
	}
}

DP[j][i]는 j위치부터 i위치까지의 값을 찾는 것을 의미합니다.

그리고 현재 DP[j][i]와 DP[j][k] + DP[k+1][i] 중 작은 값을 DP[j][i]에 넣습니다.

여기서 DP[j][k] + DP[k+1][i]는 

DP[j][i]를 두 부분으로 나눈것입니다.

가운데를 잘라서 왼쪽부분이 DP[j][k] 오른쪽 부분이DP[k+1][i]입니다.

 

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

int DP[510][510];
int arr[510];
int sum[510];

int main()
{
	int testcase;
	cin >> testcase;

	while (testcase--)
	{
		memset(DP, 0, sizeof(DP));
		memset(arr, 0, sizeof(arr));

		int n;
		cin >> n;

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

		for (int i = 2; i <= n; ++i)
		{
			for (int j = i - 1; j > 0; --j)
			{
				DP[j][i] = 987654321;
				for (int k = j; k <= i; k++)
					DP[j][i] = min(DP[j][i], DP[j][k] + DP[k + 1][i]);

				DP[j][i] += sum[i] - sum[j - 1];
			}
		}
		cout << DP[1][n] << endl;

	}
	return 0;
}