[Algorithm] cpp 백준 13263번 : 나무 자르기

증가하는 높이 a와 감소하는 비용 b의 단조성을 활용해 점화식 dp[i]=min_{j<i}(dp[j]+b[j]*a[i])의 하한선을 직선 하포로 관리하고, CHT(단조 큐)로 O(n) 시간에 계산합니다. 교차 지점 비교와 128비트 연산으로 오버플로를 방지하며 구현 포인트와 정당성을 간명히 정리했습니다.

문제

링크: https://www.acmicpc.net/problem/13263
요약: 높이 배열 a와 충전 비용 배열 b가 각각 엄격 증가/감소합니다. 모든 나무를 0이 될 때까지 자를 때 필요한 총 충전 비용의 최솟값을 구합니다.

입력/출력

1
2
3
4
5
6
7
<입력>
n
a1 a2 ... an
b1 b2 ... bn

<출력>
최솟값

예시

접근 개요

핵심 점화식: dp[i] = min_{j<i} (dp[j] + b[j] * a[i]).
단조성: a는 엄격 증가, b는 엄격 감소 → 기울기 감소 직선 집합, 질의 x=a[i] 증가.
최적화: Convex Hull Trick을 단조 큐(two-pointer)로 구현해 각 a[i]에 대한 최소값을 O(1) 평균으로 갱신, 전체 O(n).

알고리즘 설계

선형함수 y = m x + c를 m=b[j], c=dp[j]로 해석하고, 최소 하한선(lower envelope)을 유지합니다.
두 직선의 교차 비교를 정수 산술로 처리하여 부동소수 오차를 제거합니다. 값 계산은 __int128 중간 연산으로 오버플로를 방지합니다.
정당성: a 증가로 질의가 왼→오 순서, b 감소로 기울기 단조 → 최적 직선 인덱스는 절대 뒤로 이동하지 않음. 따라서 앞선 직선을 유지하는 단조 큐로 전역 최소가 보장됩니다.

의사코드 요약

1
2
3
4
5
6
7
8
9
dp[1] = 0
hull = [{m=b[1], c=dp[1]}]; head=0
for i in 2..n:
    while head+1<hull.size and f(hull[head], a[i]) >= f(hull[head+1], a[i]): head++
    dp[i] = f(hull[head], a[i])
    cur = {m=b[i], c=dp[i]}
    while hull.size-head >= 2 and isBad(hull[-2], hull[-1], cur): pop_back()
    push_back(cur)
answer = dp[n]

복잡도

시간: O(n)
공간: O(n)

구현 (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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Line { long long m, b; };

static inline __int128 eval128(const Line& l, long long x) {
    return (__int128)l.m * x + l.b;
}

static inline bool isBad(const Line& l1, const Line& l2, const Line& l3) {
    // (c2 - c1)/(m1 - m2) >= (c3 - c2)/(m2 - m3)  → l2는 필요 없음
    return (__int128)(l2.b - l1.b) * (l2.m - l3.m) >= (__int128)(l3.b - l2.b) * (l1.m - l2.m);
}

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

    int n; cin >> n;
    vector<long long> a(n + 1), b(n + 1), dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    // dp[i] = min_{j<i} (dp[j] + b[j] * a[i])
    vector<Line> hull; hull.reserve(n);
    hull.push_back({b[1], dp[1]});
    int head = 0;

    for (int i = 2; i <= n; ++i) {
        while ((int)hull.size() - head >= 2 && eval128(hull[head], a[i]) >= eval128(hull[head + 1], a[i])) {
            ++head;
        }
        dp[i] = (long long)eval128(hull[head], a[i]);

        Line cur{b[i], dp[i]};
        while ((int)hull.size() - head >= 2 && isBad(hull[(int)hull.size() - 2], hull.back(), cur)) hull.pop_back();
        hull.push_back(cur);
    }

    cout << dp[n] << '\n';
    return 0;
}