https://www.acmicpc.net/problem/13263
13263번: 나무 자르기
첫째 줄에 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을 만족
www.acmicpc.net
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;
}
'Problem Solving > Convex Hull Trick' 카테고리의 다른 글
[백준] 12795번: 반평면 땅따먹기 (0) | 2023.03.10 |
---|---|
[백준] 14240번: 부분 수열의 점수 (0) | 2023.03.06 |
[백준] 6171번: 땅따먹기 (0) | 2023.03.06 |
[백준] 4008번: 특공대 (0) | 2023.03.06 |
[백준] 23282번: Line Fighter 2 (0) | 2023.03.05 |