백준 11066 - 파일 합치기

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int INT_MAX_NUM = 1000000007;
int k[501]; //페이지 값
int dp[501][501]; //0~n까지 최소 값
int sum[501]; //0~n까지 페이지 더한 값

int main() {

    int T;
    int K;
    int i,j;

    scanf("%d", &T);

    while(T--){
        scanf("%d", &K);
        sum[0] = 0;
        for (i = 1; i <= K; i++) {
            scanf("%d", &k[i]);
            sum[i] = sum[i - 1] + k[i];
        }

        for (i = 1; i < K; i++) { //dp 구하기
            for (int kx = 1; kx + i <= K; kx++) { //kx가 더하는 기준점 (두 구역으로 나누기)
                int ky = kx + i;
                dp[kx][ky] = INT_MAX_NUM; //가장 큰 값 넣어주기 (항상 갱신되도록)

                for (int mid = kx; mid < ky; mid++) { //ky는 위에서 정해줬음, 두 구역 중 뒷부분 더하기
                    dp[kx][ky] = min(dp[kx][ky], dp[kx][mid] + dp[mid + 1][ky] + sum[ky] - sum[kx - 1]); 
                    //왼쪽 구역 + 오른쪽 구역(합치는 비용) + 더한 값 누적 - 맨 앞에꺼 더한 값 누적
                }
            }
        }
        printf("%d\n", dp[1][K]);
    }

    return 0;
}