(c++)백준 11066번: 파일 합치기

www.acmicpc.net/problem/11066

11066번: 파일 합치기

[풀이]

DP로 풀 수 있는 문제였다.

DP[i][j] : i번째 장부터 j번째 장까지 어떤 순서로 합쳐야 최소비용이 나오는지(그 때의 최소비용)

Sum[i] : 1장 ~ i장 비용 합

점화식

DP[i][[j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Sum[j] - Sum[i-1]) (여기서 Sum[j] - Sum[i-1]은 i~j번째 장을 최종으로 합칠 때 드는 비용, k는 몇번째 장에서 끊을지)

재귀를 사용하였다.

 

 

#include <iostream>
#include <cstring>//memset
#include <algorithm>//min
using namespace std;

int K;
int C[501];
int Sum[501];
int DP[501][501];

int solution(int s, int e) {
	//s가 e보다 크거나 같아지면
	if (s >= e)
		return 0;
	//두 장만 남았으면
	if (s + 1 == e)
		return C[s] + C[e];

	int &res = DP[s][e];
	//이미 최소 비용 구해놨으면 반환해줌
	if (res != -1)
		return res;
	res = 99999999;
	for (int i = s; i <= e; i++) {
		res = min(res, solution(s, i) + (solution(i + 1, e) + Sum[e] - Sum[s - 1]));
	}
	return res;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> K;
		memset(Sum, 0, sizeof(Sum));
		memset(DP, -1, sizeof(DP));
		for (int i = 1; i <= K; i++) {
			cin >> C[i];
			Sum[i] = Sum[i - 1] + C[i];
		}
		cout << solution(1, K) << '\n';
	}
	return 0;
}