백준 11066 파일 합치기 (C++)

11066번: 파일 합치기

전형적인 메모이제이션을 활용한 동적 프로그래밍 문제이다. 오랜만에 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;
}