파일 합치기

인접한 파일들끼리 합쳐 새 파일을 만들 수 있으며 이 때 합치는 비용은 양 파일 크기의 합이다. 적절한 순서로 합쳐 최소 비용으로 파일을 하나로 만들어보자.

발상 1

우선 동적 계획법 1 설명에서 했던 것처럼 인덱스를 인자로 잡아 현재까지의 최적값을 저장하는 방식으로 풀어보자. 기저 사례는 파일 개수가 2인 경우고 이 때, 합치는 비용은 $A_{0} + A_{1}$ 이다. 새로운 파일 $A_{i}$ 가 들어왔을 때 우리는 이 파일을 단일로 이전 덩어리 $A_{0} \sim A_{i - 1}$ 에 추가한 비용과 바로 이전의 파일 $A_{i - 1}$ 과 합친 뒤 $A_{0} \sim A_{i - 2}$ 구간에 추가한 비용 중 작은 쪽을 선택해나가면 전체 구간의 최적값도 구할 수 있을 것 같다.

발상 1 해킹

잘 생각해보면 발상 1에는 허점이 있다. 파일을 합치는 방식은 현재 파일을 이전 덩어리 전체에 추가하는 방식과 이전 파일과 합친 뒤 이전 덩어리 전체에 추가하는 방식만 있는 것이 아니다.
이전 덩어리 전체가 아닌 이전 덩어리의 일부와 먼저 합친 다음, 남은 덩어리와 합치는 식으로 무수히 많은 조합법이 있다. 더하는 구간 뿐 아니라 순서에 따라서도 계산 결과가 달라지기 때문에 단순히 이전 전체 구간에 더하는 방식으로는 최적값을 구할 수 없다.

5 4 3 2 1

이 예제에서 5번 파일을 더할 때는 dp(5 4 3 2) + 1 와 dp(5 4 3) + 2 + 1 두 가지 경우만 고려하게 된다. 하지만 답은 dp(dp(5 4) dp(3 dp(2 1))) 이다. $i$ 번째까지의 최적값을 구할 때 $i - 1$ , $i - 2$ 번째 최적값만 필요한 것이 아니기 때문에 이 방식으로는 답을 수할 수 없다.

발상 2

파일은 한번에 2개씩만 합칠 수 있으므로 어떤 구간 $s \sim e$ 를 이루는 모든 조합은 $s \sim k$ 와 $(k + 1) \sim e$ 두 구간으로 다시 나눌 수 있다. 즉, 구하고자하는 전체 구간 $1 \sim n$ 에 대해 재귀적으로 구간을 나눠가며 양쪽 구간의 합이 최소가 되는 경우를 찾으면 된다. 기저 사례는 구간 크기가 2인 경우다. 1로 해도 상관은 없지만 이왕이면 재귀 호출 횟수를 줄일 수 있도록 2로 설정하는 것이 좋다. 인자는 구간의 시작 / 끝 2개이며 다음과 같은 점화식을 작성할 수 있다.

점화식

{n_{s, e} = s, e 구간을 하나로 합치는 최소 비용 a_{i} = i 번째 파일 크기

n_{s, e} = k = s \to e - 1 min (n_{s, k} + n_{k + 1, e}) + i = s \sum e a_{i}

마지막에 구간 파일 크기의 합을 따로 더하는 이유는 누적 비용을 구해야하기 때문이다.

5 4 3 2 1

이 예제에서 5와 4를 더해 크기 9의 파일을 만들었다 하자. 이후에 이 파일을 다른 파일과 합칠 때 단순히 파일 크기 9만 비용으로 추가하는 것이 아닌 크기 9의 파일을 만들기 위해 먼저 지불했던 9의 비용도 별도로 합산해 총 비용은 18이 된다. 그렇다면 구간의 최적값의 2배를 하지 않고 왜 구간의 파일 크기의 합만을 더하는 걸까? 구간의 최적값은 구간 2개만 합치는 비용이 아닌 구간을 하나의 파일로 만들기 위한 누적비용이기 때문이다. 이 2가지 비용을 구분해야 한다. 누적 비용은 현재 2개의 구간을 합치는 비용 + 현재 2개의 구간을 만들기 위해 사용한 비용이다. 위의 점화식에서 계산을 한 값이 바로 현재 2개의 구간을 만들기 위해 사용한 비용이고 현재 2개의 구간을 합치는 비용은 순수하게 두 파일의 크기의 합이다. 이 부분이 상당히 헷갈리기 때문에 주의해야 한다.

코드 ( Top-Down )

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int n;
vector<int> arr, ps;
vector<vector<int>> dp; //dp[s][e] = s~e 구간을 합치는 최소 비용
int r(int s, int e) {
    if (dp[s][e] != -1) return dp[s][e]; // 이미 계산한 구간이면 skip
    int mn = 21e8;
    for (int i = s; i < e; i++) {
	    // 왼쪽 구간 최소 비용 + 왼쪽 구간 파일 크기 합
        int s1 = (i == s) ? arr[s] : r(s, i) + ps[i] - ps[s - 1];
	    // 오른쪽 구간 최소 비용 + 오른쪽 구간 파일 크기 합
        int s2 = (i + 1 == e) ? arr[e] : r(i + 1, e) + ps[e] - ps[i];
        mn = mn < s1 + s2 ? mn : s1 + s2;
    }
    return dp[s][e] = mn;
}
int main() {    
    int tc; cin >> tc;
    while (tc--) {
        cin >> n; arr = vector<int>(n + 1); ps = vector<int>(n + 1); dp = vector<vector<int>>(n + 1, vector<int>(n + 1,  -1));
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            ps[i] = ps[i - 1] + arr[i];
        }                      
        cout << r(1, n) << "\n";
    }
    return 0;
}

코드 ( Bottom-Up )

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int tc; cin >> tc;
    while (tc--) {
        int n; cin >> n; vector<int> arr(n + 1), ps(n + 1); vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            ps[i] = ps[i - 1] + arr[i];
        }              
        for (int k = 1; k < n; k++) { // k = 구간 크기
            for (int i = 1; i <= n - k; i++) { // i = 구간 시작 인덱스
                int j = i + k; // 구간 종료 인덱스
                int mn = 21e8;
                for (int p = i; p < j; p++) { // 구간을 둘로 나누고 최소 비용 계산
                    int s1 = dp[i][p] + ps[p] - ps[i - 1];
                    int s2 = dp[p + 1][j] + ps[j] - ps[p];
                    mn = mn < s1 + s2 ? mn : s1 + s2;
                }
                dp[i][j] = mn;                
            }
        }        
        cout << dp[1][n] << "\n";
    }
    return 0;
}

🪴 Quartz 4.0

Explorer