[C++] 백준 11066 파일 합치기

11066 파일 합치기

11066번: 파일 합치기

C++

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

typedef long long ll;

int w[503];
int sum[503];
int DP[503][503];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int k;
        cin >> k;
        for (int i = 1; i <= k; ++i) {
            cin >> w[i];
            sum[i] = sum[i - 1] + w[i];
        }

        for (int len = 1; len < k; len++) {
            for (int i = 1; i <= k; i++) {
                int j = i + len;
                if (j > k) break;

                DP[i][j] = INF;
                for (int mid = i; mid < j; mid++)
                    DP[i][j] = min(DP[i][j], DP[i][mid] + DP[mid + 1][j] + sum[j] - sum[i - 1]);
            }
        }

        cout << DP[1][k] << '\n';
    }

    return 0;
}

 

11049 행렬 곱셈 순서와 흡사한 방법으로 풀 수 있다.

DP[i][j]를 구간 [i, j]에서의 최소 비용이라 하면,

DP[i][j] = mid가 i부터 j까지 이동할 때 (DP[i][mid] + DP[mid+1][j] + (i~j 까지의 합))의 최솟값이라 나타낼 수 있다.

 

이때 (i~j까지의 합)은 sum[j] - sum[i-1]으로 나타낼 수 있다.