BOJ 11066 - 파일 합치기(DP)

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

11066번: 파일 합치기

- 여러 개의 파일을 1개가 남을 때까지 합쳤을 때의 최소비용을 구하는 문제이다. 
- 페이지를 합치는 부분문제들의 합을 구해야되므로, overlapping subproblem이 있고, 그 중 최소값을 구해야되므로 
optimal substructure에 해당된다. 그래서 DP로 접근할 수 있다. - 탑다운 방식

#include <cstring>
#include <iostream>
using namespace std;
#define endl '\n'
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int t;
int a[501];
int d[501][501];  // i부터 j까지 합치는 최소비용
// i ~ k ~ j
//d[i][j] =  min(d[i][k] + d[k+1][j]) + 전체비용, i <= k < j

int go(int s, int e) {
    if (s == e) return 0;  // 파일 1개
    if (d[s][e] != -1) return d[s][e];

    int sum = 0;
    int& ans = d[s][e];
    for (int i = s; i <= e; ++i) {
        sum += a[i];
    }

    for (int k = s; k <= e - 1; ++k) {
        int tmp = go(s, k) + go(k + 1, e) + sum;
        if (ans == -1 || ans > tmp) ans = tmp;
    }

    return ans;
}

int main() {
    FASTIO;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;  // 500장
        for (int i = 1; i <= k; ++i) {
            cin >> a[i];
        }

        memset(d, -1, sizeof(d));
        cout << go(1, k) << endl;
    }

    return 0;
}

 

- 바텀업

#include <cstring>
#include <iostream>
using namespace std;
#define endl '\n'
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)
#define INF 0x3f3f3f3f

int a[501];
int psum[501];
int d[501][501];  // i~j까지 합칠때 최소비용
// d[i][j] = d[i][k] + d[k+1][j] + a[i]~a[j]까지의 합, (i-j > 2)
// d[1][5] = d[1][2] + d[3][5] + (a[1]~a[5]) 까지 부분합
//         = d[1][3] + d[4][5] + (a[1]~a[5]) 까지의 부분합
// d[1][2] = a[1] + a[2]

int main() {
    FASTIO;
    int t;
    cin >> t;

    while (t--) {
        memset(d, INF, sizeof(d));
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            psum[i] = psum[i - 1] + a[i];
            d[i][i] = 0;
        }

        for (int k = 1; k < n; ++k) {
            for (int i = 1; i <= n - k; ++i) {
                int& target = d[i][i + k];

                for (int j = i; j < i + k; ++j) {
                    target = min(target, d[i][j] + d[j + 1][i + k]);
                }

                target += psum[i + k] - psum[i - 1];
            }
        }

        cout << d[1][n] << endl;
    }

    return 0;
}