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

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

13263번: 나무 자르기

---

1. 문제 조건

1) 나무 N 개를 모두 잘라야 한다.

2) 전기톱을 한 번 사용하면, 그 나무의 높이는 1 줄어든다.

3) 전기톱을 사용할 때마다 전기톱을 충전해야 한다.

4) 충전 비용은 높이가 0이 된 나무 중 가장 큰 번호에 해당하는 비용이다.

5) 모든 나무를 자르는 데 필요한 총 비용의 최솟값을 출력한다.

6) 높이는 번호가 커질수록 커진다. $( height[i-1] < height[i] ) $

7) 비용은 번호가 커질수록 줄어든다. $( cost[i-1] > cost[i] )$

8) 맨 처음 나무의 높이는 항상 1이다.

9) 맨 마지막 비용은 항상 0이다.

 

2. dp 배열 정의

이 문제의 핵심은 마지막 나무를 완전히 자르는 것에 있다.

마지막 나무를 자르고 나면, 충전 비용은 항상 0이 된다.

따라서 마지막 나무를 자르기만 하면,

나머지 나무가 얼마나 남았든지 공짜로 다 잘라버릴 수 있다.

 

따라서 dp 배열을 n번째 나무를 베는데 드는 최소 비용으로 정의한다.

#define MAXN 100001

typedef long long ll;

// dp[n] = n번째 나무를 완전히 자르는 데 드는 최소 비용
ll dp[MAXN];

ll height[MAXN];
ll cost[MAXN];

 

3. 점화식

$dp[n]$ 을 구하기 위한 점화식을 생각해보자.

문제에서는 $n$이 마지막 인덱스가 아니라면 n번째 비용이 0이 될 수 없지만,

우리는 $dp[n]$ 을 전체 나무의 개수가 $n$개라고 생각하여 $cost[n] = 0$ 이라고 가정하자.

 

하나 더, 첫 번째 나무의 높이는 항상 1인데 전혀 의미 없는 값이다.

왜냐하면 완전히 잘린 나무가 있어야만 충전을 할 수 있는데

시작하자마자 첫 번째 나무를 자르지 않으면 충전 자체가 불가하다.

따라서 첫 번째 나무를 반드시 잘라야 한다.

그러면 초기 충전 비용은 반드시 $cost[1]$ 이 된다.

 

점화식을 구하기 위해 몇 가지 경우를 생각해보자.

 

1) $dp[1]$

- 나무가 모두 1개일 때, 1번째 나무를 완전히 자르는 최소 비용이다.

- 1번째 나무의 높이는 1이고 처음에는 완전히 충전되어 있으므로 $dp[1] = 0$ 이다.

 

2) $dp[2]$

- 나무가 모두 2개일 때, 2번째 나무를 완전히 자르는 최소 비용이다.

- $dp[2] = dp[1] + height[2] \times cost[1]$ 이다.

 

3) $dp[3]$

- 나무가 모두 3개일 때, 3번째 나무를 완전히 자르는 최소 비용이다.

- $dp[3] = dp[1] + height[3] \times cost[1]$ 또는 $dp[3] = dp[2] + height[3] \times cost[2]$ 이다.

- 위 2개의 값 중 최솟값을 $dp[3]$ 에 저장하면 된다.

 

즉, $0\leq  j < i$ 인 모든 $j$에 대해 최솟값을 $dp[i]$ 에 저장하면 된다.

$$dp[i] = min(dp[j] + height[i] \times cost[j]) \; (0 \leq j < i)$$

 

이제 시간 복잡도를 생각해보자.

위 점화식은 모든 $i$에 대해 $i$ 미만의 모든 $j$를 확인하고 있다.

따라서 시간 복잡도는 $O(N^2)$ 이 나온다.

 

그런데 문제에서 주어진 $N$의 최댓값은 100,000 이다.

그렇다면 어림잡아 100,000 × 100,000 = 10,000,000,000 이라는 어마무시한 숫자가 나온다.

대충 봐도 시간 초과가 날 것이 분명하다.

 

그렇다면 이 문제는 풀 수 없는 걸까?

 

4. Convex Hull Trick

다행히 우리는 Convex Hull Trick (CHT) 라는 최적화 기술을 쓸 수 있다.

Convex Hull Trick 에 대한 자세한 내용은 다른 포스트에서 다루기로 한다.

 

CHT 는 dp 의 점화식이 아래와 같은 꼴을 하는 경우에 사용할 수 있다.

$$dp[i] = min(A[i] \times B[j] + C[j]) \; (B[i-1] \geq B[i])$$

위에서 찾아낸 이 문제의 점화식을 함께 관찰해보자.

$$dp[i] = min(dp[j] + height[i] \times cost[j]) \; (0 \leq j < i)$$

 

$A[i] = height[i]$, $B[j] = cost[j]$, $C[j] = dp[j]$ 로 각각 대응시킬 수 있다.

 

우리는 CHT 를 이용해서, $A[i]$ 를 $x$로 대신 쓸 수 있다.

그러면 위 점화식은 $B[j] \times x + C[j]$ 꼴이 되고, 1차 함수의 모양이 된다.

 

CHT 를 적용할 때, 이 문제만의 특수한 조건이 하나 더 있다.

바로 $B[j]$가 감소 함수이며, $A[i]$가 증가 함수라는 점이다.

즉, 위 점화식을 1차 함수로 생각했을 때 $j$가 증가할수록 기울기가 감소한다.

더불어 $x$ 역할을 하는 $A[i]$는 커지는 방향으로만 이동하므로,

$x$ 보다 작은 값에 속하는 직선은 더 이상 볼 필요가 없다.

 

우리는 이제 각 $dp[i]$ 에 해당하는 직선들만 잘 관리해주면 된다.

우선 직선을 나타내는 구조체를 만들자.

// y = a * x + b
struct Line {
	ll a, b;
};

Line 구조체는 2개의 변수를 갖는다.

$a$는 $x$의 계수이며, $b$는 $y$ 절편이다.

다시 한 번, $a = B[j] = cost[j]$ 이고 $b = C[j] = dp[j]$ 임을 잊지 말자.

 

마치 Convex Hull 알고리즘 중 Graham's scan 때와 비슷하게

우리는 Line 을 stack 또는 deque 형태로 관리할 것이다.

Line deq[MAXN];
int s, e;	// deq 의 시작과 끝 인덱스

 

새로운 Line 이 들어오면서 이전에 저장된 Line 이 더 이상 쓸모가 있는지 없는지 판단해주어야 한다.

만약 $top - 2$ 번째 직선과 $top - 1$ 번째 직선 교점의 x좌표가

$top - 1$ 번째 직선과 $top$ 번째 직선 교점의 x좌표보다 크거나 같다면

$top - 1$ 번째 직선은 더 이상 쓸모가 없다.

 

그림으로 그려보면 쉽게 이해가 가능한데,

이는 CHT 포스트에서 자세히 다루도록 한다.

위 내용을 기반으로 Line 을 deque 에 넣는 함수를 작성한다.

// deq[a] 와 deq[b] 직선 교점의 x 좌표를 구하는 함수
double crossX(int a, int b) {
	return 1.0 * (deq[a].b - deq[b].b) / (deq[b].a - deq[a].a);
}

void insert(Line line) {
	// deq 원소 개수가 1개는 보장되도록 한다.
	while((s + 1 < e) && crossX(e-2, e-1) >= crossX(e-1, e)) {
    	deq[e-1] = deq[e];
        e--;
    }
    e++;
}

Convex Hull 알고리즘과 비슷하다는 느낌을 받으면 좋다.

 

이제 초기 직선을 넣어주자.

초기 직선은 $i = 0$ 일 때를 말한다.

따라서 $a = B[0] = 0$, $b = C[0] = dp[0]$ 이 된다.

그리고 나서 deq 에 초기 직선을 넣어주면 준비가 끝난다.

Line line;
line.a = 0, line.b = 0;
insert(line);

 

이제 1부터 N 까지 순회하며 직선을 만들어 넣어주면 된다.

직선을 만들기 전에, $i$번째에 해당하는 $dp[i]$를 계산하는 것을 잊지 말자.

 

$dp[i]$는 주어진 $x = A[i] = height[i]$ 를 포함하는 직선의 값으로 결정된다.

Convex Hull Trick 에 따라, deq 에 저장된 직선들을 교점 기준으로 선택하면 된다.

즉, $height[i]$가 포함된 직선을 찾아서 $y = a \times x + b$ 를 계산하면 된다는 말이다.

 

보통 CHT 는 $height[i]$ 가 포함된 직선을 찾을 때 binary search 를 사용한다.

그러나 이 문제의 경우 기울기인 $B[j] = cost[j]$가 0이 될 때까지 감소하고

$x = height[i]$ 가 계속 증가하므로,

스위핑을 사용해서 $O(N)$ 만에 해결할 수 있다.

즉, 지금 $x = height[i]$ 보다 작은 곳의 범위를 포함하는 직선은 볼 필요조차 없다는 것이다.

ll query(ll x) {
	while((s + 1 < e) && crossX(s, s+1) <= x) s++;
    
    return deq[s].a * x + deq[s].b;
}

 

위 쿼리 함수를 사용해서 $dp[i]$ 값을 계산한 후에는

다음 직선을 만들어서 넣어주면 된다.

dp[i] = query(height[i]);

line.a = cost[i];
line.b = dp[i];
insert(line);

CHT 를 사용하지 않았을 때는 무려 $O(N^2)$ 시간이 걸리지만

CHT 를 사용하면 $O(N log N)$, 이 문제의 경우 $O(N)$ 시간만에 풀 수 있다.

 

마지막으로 $dp[N]$ 의 값을 출력하면 정답이 된다.

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXN 100001

typedef long long ll;

// y = a * x + b
struct Line {
    ll a, b;
};

ll height[MAXN];
ll cost[MAXN];
ll dp[MAXN];

Line deq[MAXN];
int s, e;

double crossX(int a, int b) { return 1.0 * (deq[a].b - deq[b].b) / (deq[b].a - deq[a].a); }

void insert(Line line) {
    deq[e] = line;

    while(s + 1 < e && crossX(e - 2, e - 1) >= crossX(e - 1, e)) {
        deq[e-1] = deq[e];
        e--;
    }
    e++;
}

ll query(ll x) {
    while(s + 1 < e && crossX(s, s+1) <= x) s++;

    return deq[s].a * x + deq[s].b;
}

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

    int N; cin >> N;
    for(int i=1; i<=N; i++) cin >> height[i];
    for(int i=1; i<=N; i++) cin >> cost[i];

    Line line;
    line.a = 0, line.b = 0;

    s = e = 0;
    insert(line);

    for(int i=1; i<=N; i++) {
        dp[i] = query(height[i]);

        line.a = cost[i];
        line.b = dp[i];
        insert(line);
    }

    cout << dp[N] << '\n';

    return 0;
}