[Algorithm] cpp 백준 13261번: 탈옥 - DP 분할정복 최적화

연속한 L칸을 G개의 구간으로 분할해 각 구간 비용을 (길이×구간합)으로 정의하고 총합을 최소화합니다. dp[g][r]=min(dp[g-1][k]+cost(k+1,r))를 이용해 분할정복 최적화로 O(G·L·logL)에 해결하며, 누적합으로 O(1) 구간비용·경계·64비트 오버플로를 꼼꼼히 점검합니다.

문제

링크: https://www.acmicpc.net/problem/13261
요약: 길이 \(L\)의 칸마다 탈옥력 \(C_i\)가 주어집니다. 간수 최대 \(G\)명을 배치해 연속 구간 단위로 감시할 때, 구간 \([l,r]\)의 비용은 \((r-l+1)\times\sum_{i=l}^{r} C_i\) 입니다. 전체 비용의 최솟값을 구합니다.

입력/출력

1
2
3
4
5
6
<입력>
L G
C1 C2 ... CL

<출력>
최솟값

접근 개요

핵심 관찰: 한 간수가 맡는 범위는 연속 구간이며, 구간 비용은 길이와 구간합의 곱으로 표현됩니다.
모델링: \(dp[g][r] =\) 처음 \(r\)칸을 \(g\)개의 구간으로 나눴을 때의 최소 비용.
전이: \(dp[g][r] = \min_{0\le k
최적화: 비용 구조가 단조 최적해(Argmin)가 \(r\)에 대해 비내림차순이므로 Divide and Conquer Optimization 적용. 각 레이어를 \(O(L\log L)\)에 계산.

flowchart LR
  A[Prefix Sum S[i] 계산] --> B[비용 cost(l,r) = (r-l+1)(S[r]-S[l-1])]
  B --> C[dp[g][r] = min_k dp[g-1][k] + cost(k+1,r)]
  C --> D[Argmin 단조성]
  D --> E[Divide & Conquer Optimization로 레이어 g 계산]

알고리즘 설계

전처리: \(S[i]=\sum_{t=1}^{i} C_t\)
전이 비용: cost(l,r) = (r-l+1) * (S[r]-S[l-1])를 O(1)에 계산
점화식: dp[g][r] = min_{k<r} dp[g-1][k] + cost(k+1, r)
D&C 계산: compute(l, r, optL, optR)로 구간의 중간 mid 최적 분할점 k를 optL..min(mid-1,optR)에서 찾고, 좌/우로 opt 범위를 좁혀 재귀
복원 불필요: 값만 요구되므로 경로 추적은 생략
자료형: 비용 상한이 약 6.4e16이므로 64-bit 정수 사용

복잡도

시간: \(O(G\cdot L\log L)\)
공간: \(O(L)\)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

static const long long INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, G;
    if (!(cin >> L >> G)) return 0;
    G = min(G, L);

    vector<long long> C(L + 1, 0);
    for (int i = 1; i <= L; ++i) cin >> C[i];

    vector<long long> S(L + 1, 0);
    for (int i = 1; i <= L; ++i) S[i] = S[i - 1] + C[i];

    auto cost = [&](int l, int r) -> long long {
        long long len = r - l + 1;
        return len * (S[r] - S[l - 1]);
    };

    vector<long long> prev(L + 1, INF), cur(L + 1, INF);
    prev[0] = 0;

    function<void(int,int,int,int)> solve = [&](int Lx, int Rx, int optL, int optR) {
        if (Lx > Rx) return;
        int mid = (Lx + Rx) >> 1;

        long long best = INF; int bestK = -1;
        int sr = min(mid - 1, optR);
        for (int k = optL; k <= sr; ++k) {
            if (prev[k] == INF) continue;
            long long cand = prev[k] + cost(k + 1, mid);
            if (cand < best) { best = cand; bestK = k; }
        }
        cur[mid] = best;

        solve(Lx, mid - 1, optL, (bestK == -1 ? optL : bestK));
        solve(mid + 1, Rx, (bestK == -1 ? sr : bestK), optR);
    };

    for (int g = 1; g <= G; ++g) {
        fill(cur.begin(), cur.end(), INF);
        solve(1, L, 0, L - 1);
        prev.swap(cur);
        prev[0] = INF; // r>=g가 아니면 사실상 불가능 상태 유지
    }

    cout << prev[L] << '\n';
    return 0;
}

구현 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    L = next(it); G = next(it)
    G = min(G, L)
    C = [0] + [next(it) for _ in range(L)]
    S = [0]*(L+1)
    for i in range(1, L+1):
        S[i] = S[i-1] + C[i]

    INF = 1<<62
    prev = [INF]*(L+1)
    cur = [INF]*(L+1)
    prev[0] = 0

    def cost(l, r):
        return (r - l + 1) * (S[r] - S[l-1])

    sys.setrecursionlimit(1_000_000)
    def solve_layer(Lx, Rx, optL, optR):
        if Lx > Rx:
            return
        mid = (Lx + Rx) // 2
        best = INF
        best_k = -1
        sr = min(mid - 1, optR)
        for k in range(optL, sr + 1):
            if prev[k] == INF:
                continue
            cand = prev[k] + cost(k+1, mid)
            if cand < best:
                best = cand
                best_k = k
        cur[mid] = best
        solve_layer(Lx, mid-1, optL, optL if best_k == -1 else best_k)
        solve_layer(mid+1, Rx, sr if best_k == -1 else best_k, optR)

    for _ in range(G):
        for i in range(L+1):
            cur[i] = INF
        solve_layer(1, L, 0, L-1)
        prev, cur = cur, prev
        prev[0] = INF

    print(prev[L])

if __name__ == "__main__":
    solve()