[C++] 나무 자르기 (백준 13263번) - Convex Hull Trick (CHT)

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

 

이 문제의 핵심은 bn이 항상 0이라는 것이다.

bn이 0이라는 것은 마지막 나무를 완전히 자르는 순간 비용 계산은 더 이상 할 필요가 없다는 것이다. 왜냐하면 마지막 나무를 완전히 자르면 그 이후로 비용이 항상 0이기 때문이다. 즉, 우리는 마지막 나무까지 어떤 경로로 갈지(어떤 중간 나무들을 완전히 자를지)만 고민하면 된다.

 

참고로 어떤 나무를 자르다가 다른 나무를 자르고 다시 돌아와서 마저 자르고... 이런 상황은 고려할 필요가 없다. 중요한 건 최대 인덱스가 갱신되는 순간이다. 최대 인덱스가 동일하면 비용이 동일하기 때문이다.

 

암튼 우리가 구해야 하는 건 마지막 나무까지 어떤 경로로 갈지이기 때문에 그걸 바탕으로 dp를 정의해보자.

dp[i] : i번째 나무의 높이를 1로 만들기 위한 최소 비용

 

dp 점화식은 다음과 같다. 

dp[i] = min(0<=j<i) (b[j] * a[i] + dp[j])

 

점화식이 이처럼 세워지는 이유는 다음과 같다.

어떤 나무 j를 자르고 나서 나무 i를 자른다고 하면, 우선 나무 j의 높이를 1로 만들고 (여기까지의 비용이 dp[j]) 그 다음에 충전 비용이 b[j]인 상태에서 나무 i의 높이인 a[i]만큼 자르면 (여기까지의 비용이 b[j] * a[i]) 된다.

 

이 문제의 정답은 dp[n]이다. 아까도 말했듯 모든 나무를 다 자르는 비용은 마지막 나무를 다 자르는 비용과 같기 때문이다.

 

이제 dp 테이블을 채우기만 하면 되는데... 그냥 채우면 시간복잡도가 O(n^2)이다. 이런 문제를 O(nlogn)의 시간복잡도로 해결하는 방법이 있는데, Convex Hull Trick(CHT)이라고 한다.

(이 방법을 사용하기 위해서는 문제를 직선들로 표현했을 때 볼록 껍질을 이루어야 한다.)

 

이제부터 b[j]가 기울기이고, a[i]가 대입하려는 x값이고, dp[j]가 y절편인 직선을 생각해보자.

dp[2] = min(b[0] * a[2] + dp[0], b[1] * a[2] + dp[1]) 이므로 dp[2]를 구하기 위해서는 b[0] * a[2] + dp[0] 값과 b[1] * a[2] + dp[1] 값을 비교해야 한다. 이걸 그래프로 표현하면 아래와 같다.

 

이렇게 i가 증가함에 따라 line 배열에 직선들을 추가해주면 된다. 추가하는 과정에서 불필요한 line들은 pop해주면서 line 배열을 관리해주어야 한다. pop 해줘야 하는 경우는 아래와 같다.

 

line 배열에 새로운 직선을 추가해준 다음에는 dp[i] 값을 구해야 한다.

line 배열에는 아래와 같이 빨간색 볼록한 형태를 이루는 함수가 담겨있다. 이 빨간색 함수에 a[i]를 대입하면 바로 dp[i] 값을 구할 수 있다.

 

근데 a[i]를 대입하려면 여러 직선들 중 어느 직선을 사용해야 하는지를 알아야 한다. 즉, 구간들은 직선들의 교차점을 기준으로 나뉘는데, 내가 대입하려는 x값(a[i])가 어느 구간에 해당하는지를 알아야 한다.

이는 이분 탐색으로 구하면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

struct Line {
    ll a, b;
    double x;
    Line(ll a_, ll b_, double x_ = 0) : a(a_), b(b_), x(x_) {}
};

int n;
vector<int> a, b;
vector<ll> dp;
vector<Line> line;

double cross(Line &f, Line &g) {
    return (double) (g.b - f.b) / (f.a - g.a);
}

void solve() {
    int n;
    cin >> n;

    // a[i] = 나무의 높이
    a = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // b[i] = 나무에 대한 충전 비용
    b = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    // dp[i] = i번째 나무 높이를 1로 만들기 위한 최소 비용
    dp = vector<ll>(n, 0);

    for (int i = 1; i < n; i++) {
        Line f(b[i - 1], dp[i - 1]); // 새로운 line

        while (line.size() >= 1) {
            Line g = line.back(); // 가장 최근 line
            f.x = cross(f, g);
            if (f.x < g.x) line.pop_back();
            else break;
        }

        line.push_back(f); // 새로운 line 삽입

        int l = 0;
        int r = line.size();
        while (l < r) {
            int m = (l + r) / 2;
            if (line[m].x < a[i]) l = m + 1;
            else r = m;
        }

        dp[i] = line[l - 1].a * a[i] + line[l - 1].b;
    }

    cout << dp[n - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)

 

---

 

[참고] https://kibbomi.tistory.com/155