백준 11066 : 파일 합치기

 

문제 설명

---

각 장이 저장된 파일들을 하나의 파일로 합치는 과정에서, 두 파일을 합칠 때 발생하는 비용이 두 파일 크기의 합으로 주어진다. 이때, 모든 파일을 하나로 합치는 데 필요한 최소 비용을 계산하는 문제이다.

---

 

dp[i][j]: 배열 arr의 i번째 파일부터 j번째 파일까지를 합치는 데 필요한 최소 비용이라 정의한다.

 

2중 for문을 이용해 모든 구간을 검사한다. 이때 구간의 시작을 "s", 끝을 "e"라 하자.

m변수를 잡아 s~e 구간을 분할해 준다.(m = 분할지점)

 -이때 dp[s][e]는 dp[s][m] + dp[m + 1][e] + sum[e] - sum[s - 1]을 통해 갱신해준다. 구간 [s, e]를 두 부분으로 나누어 합치는 데 필요한 비용을 의미한다.

이때 필요한 sum배열은 누적합 배열로, sum[i] = 1~i까지의 합을 의미한다.

---

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[510][510];
int arr[510];
int sum[510];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        int i, j;
        int k;
        scanf("%d", &k);
        for(i=1;i<=k;i++) {
            scanf("%d", &arr[i]);
            sum[i] = sum[i - 1] + arr[i];
        }
        for(i=1;i<=k;i++) {
            for(j=1;j<=k;j++) {
                if(i == j) continue;
                dp[i][j] = 2e9;
            }
        }
        for(i=1;i<k;i++) {
            for(j=1;i + j <= k;j++) {
                int s = j;
                int e = i + j;
                for(int m = s;m<e;m++) {
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m + 1][e] + sum[e] - sum[s - 1]);
                }
            }
        }
        printf("%d\n", dp[1][k]);
    }    
    return 0;
}