[백준/C,C++] 11066번: 파일 합치기

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

풀이

문제 예제인 40, 30, 30, 50을 보겠습니다.

 

DP[start][end]를 start부터 end까지 합치는 최소비용이라 하고,

 

psum[i]를 0부터 i까지의 파일을 합치는 데 드는 비용이라 했을 때

 

40, 30, 30, 50의 최소 비용은 다음과 같이 나타낼 수 있습니다.

 

DP[1][4] = min(DP[1][1] + DP[2][4], DP[1][2] + DP[3][4], DP[1][3] + DP[4][4]) + psum[4] - psum[0]

 

DP[1][1] + DP[2][4]

DP[1][2] + DP[3][4]

DP[1][3] + DP[4][4]

 

세 가지의 경우 중 2번째 경우를 보겠습니다.

 

DP[1][2]는 40, 30을 합치는 비용인데 70입니다.

DP[3][4]는 30, 50을 합치는 비용이고 80이죠.

 

psum[4]는 40 + 30 + 30 + 50으로 150입니다.

psum[0]은 0입니다.

 

70 + 80 + 150 = 300의 값이 나오게 됩니다.

 

분할 정복으로 왼쪽 부분의 파일을 합치는 비용 + 오른쪽 부분의 파일을 합치는 비용으로 재귀 호출을 할 때

 

부분합을 더해주어야 파일을 합치는 비용이 계산됩니다.

 

위의 경우 왼쪽 부분을 합치는 비용 70, 오른쪽 부분을 합치는 비용이 80인데,

 

분할 정복 시 부분합인 150을 더해주어야 합니다.

 

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

using namespace std;

const int MAX = 501;

int cache[MAX][MAX];
int cost[MAX];
int psum[MAX];

int DP(int start, int end)
{
    // 합치는 비용 0 (하나의 파일을 합칠 수 없음)
    if (start == end) {
        return cache[start][end];
    }

    // 0이 아닌 경우 캐시 반환 (이미 최솟값이 갱신된 경우)
    if (cache[start][end] != 0) {
        return cache[start][end];
    }

    // 근접한 파일과 합치는 비용 (부분합을 더해주지 않아도 됨)
    if (end - start == 1) {
        cache[start][end] = cost[start] + cost[end];
        return cache[start][end];
    }

    // 왼쪽, 오른쪽 비용 중 가장 적은 비용 구함 (파일 간 거리가 2 이상 차이 날 경우)
    for (int mid = start; mid < end; mid++) {
        int left = DP(start, mid);
        int right = DP(mid + 1, end);
        if (!cache[start][end]) {
            cache[start][end] = left + right;
        }
        else {
            cache[start][end] = min(cache[start][end], left + right);
        }
    }

    // 부분합과 더해 반환 (합치는 과정이 2번 이상 포함되기 때문)
    return cache[start][end] += psum[end] - psum[start - 1];
}

int main(void)
{
    int T; cin >> T;

    while (T--) {
        memset(cache, 0, sizeof(cache));
        // 파일의 개수 K
        int K; cin >> K;
        for (int i = 1; i <= K; i++) {
            // 합치는 비용
            cin >> cost[i];
            // 부분합
            psum[i] = psum[i - 1] + cost[i];
        }
        cout << DP(1, K) << '\n';
    }

    return 0;
}

반례

Input

2
10
1 2 3 4 5 6 7 8 9 10
12
99 85 123 54 1 23 777 12 584 129 613 911

 

Output

173
10177