백준 - 파일 합치기 (11066) [C++]

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

 

이 문제에서 어려웠던 점은 합의 결과를 누적해서 리턴해줘야 한다는 점이다. 누적해서 리턴하지 않으면 당연히 모든 입력을 더한 값만이 나오게 된다.

누적해서 리턴하는 것을 구현하기 위해 pair<int, int> dp 배열을 사용했다. first는 실제 합한 자체의 결과이고, second는 누적 합을 저장하는 곳이다.

 

dp 테크닉 자체는 행렬 곱셈 순서에 따른 연산 수를 구하는 테크닉과 동일하다. 어떤 구간에 대해 점화식을 세워서 문제를 풀었다.

- dp[i][j] : 구간 [i, j]에서의 파일들을 하나로 합칠 때 필요한 최소 비용

- dp[i][j] : for(k : i ~ j - 1) min(dp[i][j], dp[i][k] + dp[k + 1][j])

이런식으로 점화식을 세워봤다. 물론 저대로 동작하지는 않고 대략적으로 저런 느낌일 것이라고 생각하고 문제를 풀었다.

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

#define MAX 500
#define INF 1000000000

int K;
int input[MAX];
pair<int, int> dp[MAX][MAX];

void init() {
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			dp[i][j] = { -1, -1 };
		}
	}
}

pair<int, int> solve(int start, int end) {
	if (start == end) {
		return { input[start], 0 };
	}

	if (dp[start][end].first != -1) {
		return dp[start][end];
	}

	pair<int, int> result = { INF, INF };
	for (int i = start; i <= end - 1; i++) {
		pair<int, int> left = solve(start, i);
		pair<int, int> right = solve(i + 1, end);

		int acc = left.first + left.second + right.first + right.second;

		if (result.second > acc) {
			result = { left.first + right.first, acc };
		}
	}
	return dp[start][end] = result;
}

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

	int T;
	cin >> T;
	
	for (int test_case = 0; test_case < T; test_case++) {
		cin >> K;
		for (int i = 0; i < K; i++) {
			cin >> input[i];
		}

		init();

		cout << solve(0, K - 1).second << '\n';
	}

	return 0;
}