전형적인 메모이제이션을 활용한 동적 프로그래밍 문제이다. 오랜만에 dp 문제를 풀어봤더니 굉장히 오래걸렸다. 왜 dp를 사용하는지 질문 게시판에 굉장히 좋은 설명이 나와있었다. 이 설명을 참고하길 바란다. dp 문제를 더 자주 봐야겠다. 복습이 필요하다.
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int T, K, res;
int A[501];
int cache[501][501];
int sum[501];
int dp(int start, int end) {
if (start == end) return A[start];
int& ret = cache[start][end];
if (ret != -1) return ret;
ret = INF;
int s = sum[end + 1] - sum[start];
for (int i = start; i < end; i++) {
ret = min(ret, dp(start, i) + dp(i + 1, end) + s);
}
return ret;
}
void solution() {
res = INF;
for (int i = 0; i < K - 1; i++) {
res = min(res, dp(0, i) + dp(i + 1, K - 1));
}
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
while (T--) {
cin >> K;
memset(cache, -1, sizeof(cache));
for (int i = 0; i < K; i++) {
cin >> A[i];
}
for (int i = 1; i <= K; i++) {
sum[i] = sum[i - 1] + A[i - 1];
}
solution();
}
return 0;
}