BOJ 11066 - 파일합치기 (dp)

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

점화식 어렵..

 

<문제설명> 

비용을 합치는 두 숫자의 합이라고 할 때, 숫자 배열에서 단 하나의 숫자가 남을 때 까지 인접한 두 숫자를 합칠 때의 최소 비용을 구하는 문제.

 

<풀이>

f(i,j) : i~j번째 숫자를 합할 때 비용의 최소

 

f(i, j) = f(i, k) + f(i, k+1) + psum(i, j)  (단, k=i~j-1) 중 최솟값

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 501;
const int IMP = 1e9;

int dp[MAX][MAX], a[MAX], psum[MAX], n;
int f(int i, int j) {
	if (i == j) return 0;

	int& ret = dp[i][j];
	if (ret != -1) return ret;

	ret = IMP;
	for (int k = i; k < j; k++) {
		ret = min(ret, f(i, k) + f(k + 1, j) + psum[j]-(i==0 ? 0 : psum[i-1]));
	}
	return ret;
}

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

	int tt; cin >> tt;
	while (tt--) {
		memset(dp, -1, sizeof(dp));
		memset(psum, 0, sizeof(psum));
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			psum[i] = i == 0 ? a[i] : psum[i - 1] + a[i];
		}

		cout << f(0, n - 1) << '\n';

	}
}