백준 11066번: 파일 합치기

[문제 링크]

11066번: 파일 합치기

---

연속한 페이지끼리 합쳐야된다는 것을 모르고 풀어서 고생한 문제였다.

이 사실을 알고난 후로도 풀이법을 못떠올려서 다른 사람들의 블로그를 참고했다.

다양한 방법으로 풀이해보는 것을 더 연습해야겠다.

---

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

const int INF = 987654321;
int arr[501], sum[501], memo[501][501];

int min(int a, int b) { return a < b ? a : b; }

int Topdown(int start, int end)
{
	if (start >= end) return 0;
	if (start + 1 == end) return arr[start] + arr[end];

	int& ret = memo[start][end];
	if (ret != -1) return ret;

	ret = INF;

	for (int i = start; i <= end; i++)
		ret = min(ret, Topdown(start, i) + Topdown(i + 1, end) + sum[end] - sum[start - 1]);

	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		memset(sum, 0, sizeof(sum));

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

		cout << Topdown(1, K) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 94 day