fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 13263 (C++) 나무 자르기
최초 업로드: 2025-11-03 02:01:34
최근 수정 시간: 2025-11-04 02:02:44
게시자: rlatjwls3333
카테고리: 백준
조회수: 11
# [Platinum II] 나무 자르기 [문제 링크](https://www.acmicpc.net/problem/13263) ## 문제 설명 <p>높이가 a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>인 나무 n개를 전기톱을 이용해서 자르려고 한다.</p> <p>i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 b<sub>i</sub>이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.</p> <p>나무의 높이 a<sub>i</sub>와 각각의 나무에 대한 충전 비용 b<sub>i</sub>가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비용의 최솟값을 구하는 프로그램을 작성하시오. </p> ## 입력 <p>첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>이, 셋째 줄에는 b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>이 주어진다. (1 ≤ a<sub>i</sub> ≤ 10<sup>9</sup>, 0 ≤ b<sub>i</sub> ≤ 10<sup>9</sup>)</p> <p>a<sub>1</sub> = 1이고, b<sub>n</sub> = 0이며, a<sub>1</sub> < a<sub>2</sub> < ... < a<sub>n</sub>, b<sub>1</sub> > b<sub>2</sub> > ... > b<sub>n</sub>을 만족한다.</p> ## 출력 <p>나무를 완전히 자르는 충전 비용의 최솟값을 출력한다.</p> ## 풀이 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]; } ```