백준 13263 (C++) 나무 자르기

최초 업로드: 2025-11-03 02:01:34

최근 수정 시간: 2025-11-04 02:02:44

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 나무 자르기

[문제 링크](https://www.acmicpc.net/problem/13263)

## 문제 설명

높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.

i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.

나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비용의 최솟값을 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109)

a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족한다.

## 출력

나무를 완전히 자르는 충전 비용의 최솟값을 출력한다.

## 풀이
dp[i]를 i번째 나무를 높이 1로 만드는 최소 비용으로 두고 풀었습니다. CHT를 공부할 수 있는 기초 문제입니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX = 100'001;

ll a[MAX], b[MAX], dp[MAX];

struct element {
    ll a, b;
    double x=0;
};

double meetX(element a, element b) {
    return (double)(a.b-b.b)/(b.a-a.a);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=1;i<=n;i++) cin >> a[i];
 for(int i=1;i<=n;i++) cin >> b[i];

vector<element> stk;
 for(int i=2;i<=n;i++) {
 element cur = {b[i-1], dp[i-1]};
 while(!stk.empty()) {
 cur.x = meetX(stk.back(), cur);
 if(cur.x>stk.back().x) break;
 stk.pop_back();
 }
 stk.push_back(cur);

int left=0, right=stk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(a[i]<=stk[mid].x) right=mid-1;
 else left=mid;
 }
 dp[i] = stk[left].a*a[i] + stk[left].b;
 }
 cout << dp[n];
}
```