BOJ 11066 파일 합치기

1 개요

BOJ 11066 파일 합치기

• 백준 온라인 저지 11066번 문제
• BOJ 29단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int K, temp;
int S[501];
int D[501][501];

int solve() {
    for(int i=1; i<=K; i++) {
        for(int x=1; x<=K-i; x++) {
            int y = x+i;
            D[x][y] = INT_MAX;
            for(int z=x; z<y; z++) {
                temp = D[x][z] + D[z+1][y] + S[y] - S[x-1];
                if(temp < D[x][y]) {
                    D[x][y] = temp;
                }
            }
        }
    }
    return D[1][K];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);   
    
    int T;
    cin >> T;
    while(T--) {
        cin >> K;
        for(int i=1; i<=K ;i++) {
            cin >> temp;
            S[i] = S[i-1] + temp;
        }
        cout << solve() << '\n';
    }
}