[백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I)

 분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자.

 

 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ...

 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다.

 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다.

 

 일단 탈옥 문제의 DP 식은 다음과 같다.

 i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, DP[i][j] = min(k<j) (DP[i-1][k] + (j-i)*sum(val[i+1..j]))

 여기서 변수 k는 마지막 간수(i번째 간수)가 i+1번째 칸부터 j번째 칸까지 감시를 한다고 보면 되겠다. sum 배열의 계산은 prefix sum으로 O(1)에 해주자.

 

 탈옥 문제의 DP 테이블을 직접 짜보면 문제가 어떻게 분할되는지를 이해할 수 있다. 탈옥 문제의 DP 테이블 각 셀이 서로 어떻게 연관관계를 이루고 있는지를 그려보면 다음과 같다.

 

이런 식의 그래프는 위상 정렬 문제에서도 많이 보인다. (..를 해야만 ..를 할 수 있을 때, 걸리는 시간의 최솟값은? 같은 문제)

 중요한 사실은, 파란색 점선 박스 쳐진 셀들끼리는 점화식 연관관계가 없다는 점이다. 따라서 세로줄 셀들은 한꺼번에 계산해줄 수 있다. 분할 정복이 목표로 하는 곳은 바로 이 세로줄 셀들이 되어야 한다.

 

 직접 DP 테이블을 채워보자. (예시는 백준에 있는 걸 그대로 갖고 옴) 왼쪽 값은 최솟값, 오른쪽 값은 값을 최소로 만드는 k의 최솟값이다. (즉, 값을 최소로 만드는 k가 여러 개 있으면 가장 작은 걸 선택)

6 6
11 11 11 24 26 100

i \ j	1	2	3	4	5	6
1	11 / 0	44 / 0	99 / 0	228 / 0	415 / 0	1098 / 0
2		22 / 1	55 / 1	114 / 2	199 / 3	489 / 4
3			33 / 2	79 / 3	140 / 4	299 / 5
4				57 / 3	105 / 4	240 / 5
5					83 / 4	205 / 5
6						183 / 5

 값을 최소로 만드는 k의 최솟값(이하 최적의 k값이라 하자)을 살펴보면 다음과 같은 사실을 관찰할 수 있다:

 j가 고정되어 있다면, i가 증가할 때 최적의 k값은 증가하거나 그대로이다.

 증명은... 만약 i가 1 증가했을 때 최적의 k값이 감소했다고 가정하자. 그렇다면 k(i) > k(i + 1)이다. 따라서 간수가 i명일 때 마지막 간수가 k(i)+1 ~ j만큼 담당을 하던 것이 간수가 i+1명일 때는 k(i+1)+1 ~ j만큼 담당을 하게 된다. 즉 마지막 간수가 담당하는 영역이 왼쪽으로 늘어났다. 핵심은 이렇게 왼쪽으로 늘어나는 것이 별로 좋지 않음을 보이는 것이다.

 

 함수 C(i, j)를 (j - i) * sum(val[i+1..j])라 하자. 이제 다음 사실을 증명할 수 있다.

 a <= b <= c <= d이면, C(a, c) + C(b, d) <= C(a, d) + C(b, c)

 이는 구간 두 개가 있고 한 구간이 다른 구간을 완전히 집어삼켰을 때 그렇지 않도록 풀어주는 것이 최적이라는 것을 의미한다(출처: https://koosaga.com/242). 이런 배열 C를 monge array라고 한다...고 한다. 함수 f(i, A)를 생각해보자. 이때 i는 간수의 수, A는 간수의 배치를 나타낸다. 간수의 수가 i일 때 어떤 간수의 배치 A가 있어서 f(i, A)가 최적이고, 간수의 수가 i+1일 때 어떤 간수의 배치 B가 있어서 f(i+1, B)가 최적이라면, 다음 함수

 

 g(X, Y) = f(i, X) + f(i+1, Y) (X, Y는 간수의 배치)

 

 는 X = A, Y = B일 때 최적이다. 그런데 만약 k(i) > k(i + 1)이라면 monge array의 성질에 따라 k(i)와 k(i+1)을 교환해서 A*, B*를 만들어도 g(A*, B*)는 최적이다. 그리고 이때 f(i, A*)와 f(i+1, B*) 역시 각각 최적일 수밖에 없다(왜냐하면 X, Y가 각각 독립된 변수기 때문). 이는 k(i)의 정의인, 최적을 만드는 인덱스 k의 최솟값이라는 정의에 어긋난다. 따라서 모순.

 

 (DP 식이 DP[i][j] = min(k<j) (DP[i-1][k] + C[i][j])이고 C가 monge array이면 분할 정복을 사용한 최적화를 사용할 수 있음이 잘 알려져 있다.)

 

 이 사실을 잘 이용하면 DP 셀 하나의 값을 결정할 때 굳이 1부터 j까지 열심히 iteration을 뛰어줄 필요가 없다는 사실을 알게 된다. naive한 DP에서는 column 하나의 값을 결정하기 위해 아래 그림에서 보이는 칸의 개수(jI)만큼의 iteration을 뛰어줘야 한다.

 

 

 i = I / 2를 고르자. 그리고 k = 1..j의 iteration을 뛰어주면서 k(I/2)의 값을 결정한다. 그러면 칸 개수의 후보군은 오른쪽 그림과 같이 절반 정도로 줄어든다. 큰 사각형이 작은 사각형 두 개로 잘렸다. 이 잘린 사각형들에 대해 분할을 재귀적으로 반복하면, 놀랍게도 최종적으로 탐색하는 셀의 개수는 O(jI)에서 O(jlogI) 수준으로 크게 줄어든다.

#include <bits/stdc++.h>

using i64 = long long;

struct Cell {
    i64 val;
    int opt_idx;
    
    auto operator<=>(const Cell&) const = default;
};

template<std::default_initializable T>
auto make_prefix_sum_vector(const std::vector<T>& data) noexcept
    -> std::vector<T>
{
    auto ret = std::vector<T>(data.size() + 1);
    ret[0] = T();
    for (std::size_t i = 1; i <= data.size(); ++i) {
        ret[i] = ret[i - 1] + data[i - 1];
    }
    return ret;
}

auto verdict(int I, int J, const std::vector<i64>& data) {
    I = std::min(I, J);
    auto pf_sum = make_prefix_sum_vector(data);
    auto table = std::vector(I, std::vector(J, Cell{1LL<<62, -1}));
    
    for (int j = 0; j < J; ++j) {
        table[0][j].val = pf_sum[j + 1] * (j + 1);
    }
    
    for (int i = 1; i < I; ++i) {
        for (int j = i; j < J; ++j) {
            for (int k = i - 1; k < j; ++k) {
                i64 temp = table[i - 1][k].val + (pf_sum[j + 1] - pf_sum[k + 1]) * (j - k);
                if (temp < table[i][j].val) {
                    table[i][j].val = temp;
                    table[i][j].opt_idx = k;
                }
            }
        }
    }
    
    return table;
}

auto get(int I, int J, const std::vector<i64>& data) {
    I = std::min(I, J);
    auto pf_sum = make_prefix_sum_vector(data);
    auto table = std::vector(I, std::vector(J, Cell{1LL<<62, -1}));
    
    for (int j = 0; j < J; ++j) {
        table[0][j].val = pf_sum[j + 1] * (j + 1);
    }
    
    std::function<void(int, int, int, int, int)> dnc;
    dnc = [&](int i_lbd, int i_ubd, int j, int opt_idx_lbd, int opt_idx_ubd) {
        if (i_lbd > i_ubd) {
            return;
        }
    
        int i = i_lbd + (i_ubd - i_lbd) / 2;
        for (int k = opt_idx_lbd; k <= opt_idx_ubd; ++k) {
            i64 temp = table[i - 1][k].val
                       + (pf_sum[j + 1] - pf_sum[k + 1]) * (j - k);
            if (temp < table[i][j].val) {
                table[i][j].val = temp;
                table[i][j].opt_idx = k;
            }
        }
    
        int opt_idx = table[i][j].opt_idx;
        dnc(i_lbd, i - 1, j, opt_idx_lbd, opt_idx);
        dnc(i + 1, i_ubd, j, opt_idx, opt_idx_ubd);
    };
    
    for (int j = 1; j < J; ++j) {
        dnc(1, std::min(j, I - 1), j, 0, j - 1);
    }
    
    return table;
}

void solve() {
    int I, J;
    std::cin >> J >> I;
    
    std::vector<i64> data(J);
    for (auto& n : data) {
        std::cin >> n;
    }
    
    auto table = get(I, J, data);
    std::cout << table.back().back().val << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}