백준 11066 풀이

목표: 백준 11066

환경: mac OS Mojave 10.14, CLion

로직

나한테는 대단히 어려웠던 문제, 그러나 정답률 52%

문제이해

여러 장의 소설을 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐서 최종적으로는 하나의 파일로 합친다. 파일을 합친 결과를 누적한다.

문제접근

다이나믹프로그래밍 - 문제정의, 부분합 개념

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 501;

int t;
int arr[MAX];
int pSum[MAX];
int d[MAX][MAX];

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

        for(int i=2; i<=n; i++){
            for(int j=i-1; 0 < j; j--){
                d[j][i] = (1<<30)-1;
                for(int k = j; k<i; k++)
                    d[j][i] = min(d[j][i], d[j][k]+d[k+1][i]);

                d[j][i] += pSum[i] - pSum[j-1];
            }
        }

        cout<<d[1][n]<<'\n';
    }

    return 0;
}