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

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

 

i~j의 최소비용은 i ~ m - 1 의 비용 + m ~ j 의 비용 중 제일 작은 값이다. (m은 i ~ j 사이의 값)

문제를 풀면서 여기까지는 접근했는데 합을 더해주는 부분을 생각하지 못해서 조금 헤맨 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

const int INF = 987654321;

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

	vector<int> v(501);
	int t;
	cin >> t;
	while (t--) {
		int k;
		cin >> k;
		vector<vector<int>> dp(k + 1, vector<int>(k + 1, INF));
		vector<int> sum(k + 1, 0);
		for (int i = 1; i <= k; i++) {
			cin >> v[i];
			dp[i][i] = 0;
			sum[i] = sum[i - 1] + v[i];
		}
		for (int i = k; i >= 1; i--) {
			for (int j = 1; j <= k; j++) {
				for (int y = 0; y < j; y++) {
					dp[i][j] = min(dp[i][j], dp[i][j - y - 1] + dp[j - y][j] + sum[j] - sum[i - 1]);
				}
			}
		}
		cout << dp[1][k] << "\n";
	}
};