[C++] 13263번 나무 자르기 - DP, 볼록 껍질을 이용한 최적화

1. 문제

• 높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해 자르려고 한다. 전기톱은 사용할 때 그 나무의 높이는 1만큼 감소하며, 사용할 때마다 충전해야 한다. 완전히 잘린 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘린 나무가 없다면 전기톱을 충전할 수 없다. 가장 처음에는 전기톱이 충전되어 있다.
• 나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는게 필요한 충전 비용의 최솟값을 구하시오.

<입력>

• -1-   \(n(1 \leq n \leq 100,000)\)
• -2-   a1, a2, ..., an
• -3-   b1, b2, ..., bn
  • \((1 \leq a_{i} \leq 10^{9}, 0 \leq b_{i} \leq 10^{9})\)
  • a1 = 1이고, bn = 0이며, a1 <= a2, ... , an. b1 > b2 >, ..., > bn

<출력>

• 나무를 완전히 자르는 충전 비용의 최솟값 출력

2. 재정의

• 나무는 \(a_{i}\)번 잘라야 하고, 충전 1회 비용은 \(b_{i}\) (i는 최댓값)일 때, 모든 나무를 자르기 위한 충전 비용의 최솟값을 구하시오

3. 해결방법

• bn = 0이므로, n번째 나무를 자르면 모든 나무를 무료로 자를 수 있다. 따라서 n번째 나무를 자를 때 필요한 충전 비용을 구하면 된다.
• dp를 구현할 때 나무를 완전히 자르게 될 경우 그 다음 bi에 영향을 미치므로 dp는 나무의 높이를 1로 만들 때의 비용으로 설정하여야 한다. 즉, dp(i)를 i번째 나무의 높이를 1로 만드는데 필요한 비용의 최솟값이라고 설정하면
• \(dp(i) = min(0 \leq j < i)(dp(j) + a[i]b[j])\)의 점화식을 세울 수 있게 된다.
• dp(i)는 j번째 나무를 한 번 자르고 a[i]-1번 만큼 b[j]의 가격으로 자르면 되므로 dp(j) + b[j] + (a[i]-1)*b[j] = dp(j) + a[i]b[j]가 된다.
• 이 점화식을 만족할 수 있는 이유는 dp(i)에서 i가 커질 수록 나무의 높이가 커지므로 dp(i)가 커지기 때문이다. 따라서 i=1부터 차례차례 확인하면 된다.
• 위 점화식은 \(O(n^{2})\)의 시간 복잡도(필자 생각)을 요구하므로 시간 초과된다. 따라서 Convex Hull Trick 알고리즘을 이용하여 최적화시켜야 한다.
• y = b[j] * a[i] + dp[j]를 생각해보자. x = a[i]라고 했을 때 b[j]는 j가 커질수록 감소하고 dp[j]는 증가한다. 따라서 j에 따라 직선을 그리고 최솟값만 취하게 될 경우 y = sqrt(x) 꼴의 함수를 얻을 수 있다. 여기서 x가 들어가는 직선을 고르고 그 직선의 x에 a[i]를 넣으면 dp의 최솟값을 구할 수 있다. 이 경우 \(O(nlgn)\)의 시간 복잡도로 해결할 수 있게 된다.

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int MAX_N = 100001;

// 직선을 나타내는 구조체
// f(x) = ax + b, x >= s
struct LinearFunc {
    ll a, b;
    double st;
    
    LinearFunc(): LinearFunc(1, 0){}
    LinearFunc(ll _a, ll _b): a(_a), b(_b), st(0){}
};

// <문제 조건>
// 나무의 개수 n
int n;
// 나무의 높이와 충전 비용
int a[MAX_N], b[MAX_N];

// <볼록 껍질을 이용한 최적화>
// DP
ll dp[MAX_N];
// 볼록 껍질을 이용한 최적화 알고리즘 용 직선
LinearFunc f[MAX_N];

// 두 직선 f, g의 교점의 x좌표 구하기
double CrossXloc(LinearFunc f, LinearFunc g) {
    return (g.b-f.b)/(f.a-g.a);
}

void input() {
    cin >> n;
    
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(int i=0; i<n; i++)
        cin >> b[i];
}

void Convex_Hull_Trick() {
    
    // x가 클 때 제일 작은 직선
    int top = 0;
    for(int i=1; i<n; i++) {
        // i-1번에 해당하는 새로운 직선을 top에 쌓기
        LinearFunc g(b[i-1], dp[i-1]);
        while(top > 0) {
            g.st = CrossXloc(f[top-1], g);
            if(f[top-1].st < g.st)
                break;
            // 볼록 껍질에서 교점이 더 앞에 있으면 top의 직선을 제거
            top--;
        }
        // 직선 추가
        f[top++] = g;
        
        // 나무의 높이가 일차 함수의 x값
        ll x = a[i];
        // 주어진 x좌표를 포함하는 선분(fpos)를 이분 탐색으로 찾기
        int fpos = top-1;
        if(x < f[top-1].st) {
            int lo = 0, hi = top-1;
            while(lo+1 < hi) {
                int mid = (lo+hi)/2;
                (x < f[mid].st ? hi : lo) = mid;
            }
            fpos = lo;
        }
        // dp[i] 계산
        dp[i] = f[fpos].a * x + f[fpos].b;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //컨벡스 헐 트릭 알고리즘
    Convex_Hull_Trick();
    
    cout << dp[n-1];
    
    return 0;
}

CHT알고리즘을 처음 봐서 다른 분들의 블로그를 읽어보면서 공부했다. 출처는 아래에 있다.

 

<Convex Hull Trick>

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221418495037&proxyReferer=https:%2F%2Fwww.google.com%2F 

컨벡스 헐 트릭(Convex Hull Trick)

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.