[백준/BOJ] 백준 11066번 : 파일 합치기

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

11066번: 파일 합치기

 

cache[left][right] 에 "left ~ right 파일을 합칠 때 필요한 최소 비용"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 이때, 파일의 크기를 누적합으로 psum에 저장해 놓고, cache[left][right]의 값을 구할 때, left에서 right-1 값 중 하나를 mid로 확인해 나아가며, 'cache[left][right] = cache[left][mid] + cache[mid + 1][right] + psum[right + 1] - psum[left]' 를 통해 최솟값의  cache[left][right]의 값을 구했다.

 

코드

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

int t;
int k;
vector<int> costs;
vector<int> results;
vector<int> psum;
int cache[505][505]; //[left][right] = left ~ right 파일을 합칠때 최소 비용

void pre() {
	costs.clear();
	psum.clear();

	for (int i = 0; i < 505; i++) {
		for (int j = 0; j < 505; j++) {
			cache[i][j] = -1;
		}
	}
}

int solve(int left, int right) {

	int& ret = cache[left][right];

	if (ret != -1) {
		return ret;
	}

	if (left == right) {
		ret = 0;
		return ret;
	}

	ret = numeric_limits<int>::max();

	for (int mid = left; mid < right; mid++) {
		ret = min(ret, solve(left, mid) + solve(mid + 1, right) + psum[right + 1] - psum[left]);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		pre();

		cin >> k;

		int sum = 0;
		psum.push_back(sum);

		for (int i = 0; i < k; i++) {
			int cost;
			cin >> cost;

			costs.push_back(cost);

			sum += cost;
			psum.push_back(sum);
		}

		int result = solve(0, k - 1);
		results.push_back(result);
	}

	for (int i = 0; i < results.size(); i++) {
		cout << results[i] << "\n";
	}

	return 0;
}