백준 11066 c++ : DP

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void input_data(vector<int>& C) {
	cout << "\ninput_data()\n";

	int K, i, c;
	
	cin >> K;
	for (i = 0; i < K; i++) {
		cin >> c;
		C.push_back(c);
	}

	return;
}

int find_answer(vector<int>& C) {
	cout << "find_answer()\n";
	
	int answer = 0;
	int i, j, length, K = C.size(), cost, temp;
	vector<vector<int>> DP(K, vector<int>(K, 0));
	vector<int> prefix_sum(K + 1, 0);
	
	cout << "prefix_sum : ";
	for (i = 0; i < K; i++) {
		prefix_sum[i + 1] = C[i] + prefix_sum[i];
		cout << prefix_sum[i + 1] << " ";
	}
	cout << "\n";

	//필요한 임시비용의 합?
	//합쳐진 파일들의 크기
	/*
	C1 C2 C3 C4
	40 30 30 50
	-> ((C1 + C2 = 70) + (C3 + C4 = 80) = 150) = 300이 최소 임시비용의 합
	*/

	for (length = 2; length <= K; length++) {//2개 더하기부터 시작
		for (i = 0; i <= K - length; i++) {
			temp = i + length - 1;//i번째부터 length개 더하기
			DP[i][temp] = INT_MAX;

			for (j = i; j < temp; j++) {
				cost = DP[i][j] + DP[j + 1][temp] + (prefix_sum[temp + 1] - prefix_sum[i]);
				DP[i][temp] = min(DP[i][temp], cost);
			}
		}
	}

	for (i = 0; i < K; i++) {
		for (j = 0; j < K; j++) {
			cout << DP[i][j] << " ";
		}
		cout << "\n";
	}

	answer = DP[0][K - 1];

	return answer;
}

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

	int T, i;

	cin >> T;
	for (i = 0; i < T; i++) {
		vector<int> C;
		
		input_data(C);
		cout << find_answer(C) << "\n";
	}

	return 0;
}