boj, 백준) 13263. 나무자르기 , Convex hull trick ( C / C++)

1. 문제 링크

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

13263번: 나무 자르기

 

2. 문제 개요

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

i번 나무에 전기톱을 사용할 때마다, 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다.

전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는데, 높이가 0이 되어버린 나무이고, 완전히 잘린 나무의 번호 중 최댓값이 i이면 전기톱을 충전하는 비용은  bi이 된다.

완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어 있다.

 

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

 

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

 

 

3. 문제 힌트

 

문제 개요를 쓸 때 항상 필요한 부분만 뽑아내서 쓰는 편인데 이번 문제는 모두 다 중요하다. 그래서 거의 변함이 없다.

 

dp를 사용해야 한다. dp[i]는 i번째 나무를 높이가 1이 될 때까지 자를 때의 최소비용이라고 두자.

1이 되기 전까지는 다른 나무의 비용만큼 충전할 것이다. 그런데 i번째 나무를 높이가 1이 아니고 0으로 둔다면 1->0으로 바뀐 뒤 충전할 때에는 i번째 나무의 충전비용이 들것이기 때문에 별도로 생각해주어야 한다.

 

 

4. 문제 풀이

 

이 문제의 dp 식은 dp[i] = min(0<= j < i ) a[i]b[j] + dp[j]로 나타낼 수 있다.

 

왜?라고 한다면 만약 i가 3이라고 예를 들어 보자, 어떤 j번 나무를 자르고, i번 나무를 자른다고 하자,

그렇다면,

j번 나무의 높이를 1까지만 남긴 최소 비용 (dp[j]) +

j번 나무의 높이를 0으로 하기 위해 한 번 자르는 비용(b[j]) +

i번 나무의 높이를 1까지만 남기고 자르는 비용 ((a[i]-1)b[j]) +

= dp[j] + b[j] + a[i]b[j] - b[j] = a[i]b[j] + dp[j]가 된다.

 

자 그런데 이 방식은 O(n^2)이다. N은 10만인데..

그렇다면 O(nlogn)이나 그 수준에 맞는 알고리즘을 생각해야 한다.

구글에 찾아본 결과, 보통 Convex Hull Trick이라고 CHT알고리즘이라고 많이 부른다.

 

기존의 방식대로라면 모든 i에 대하여 각각 0 <= j < i에 대해서 반복해야 한다.

CHT방식을 사용한다고 하면 모든 i에 대해 logn번 반복하면 된다.

간단한 아이디어를 이야기해보자면,

 

dp[i] = a[i]b[j] + dp[j] 에서, a[i]를 x로 보고, dp[i]를 그에 따른 함숫값(f(x))이라고 생각해보자.

그럼 f(x) = b[j]x + dp[j]과 같은 직선의 방정식처럼 둘 수 있다.

 

모든 i에 대해서 최적의 값을 가지는 직선을 가지고 있을 것이다. ( vector or stack )

 

우리가 가지고 있을 그래프

여기서 빨간색 부분이 최적의 값을 갖는 부분이고, 그 외 검은색 부분은 안 봐도 되는 부분이라고 생각하면 된다.

(빨간색 부분이 최소이기 때문)

 

자 그러면 어떻게 저 빨간색 그래프를 가지고 있을 것인지가 문제일 수도 있다.

직선을 나타내는 자료구조를 하나 만들자.

f(x) = ax + b라고 했을 때,

위의 그래프에서는 a, b를 갖는 정수 2개와, 각 그래프들은 s점들을 시작점으로 시작한다.라는 정보를 가지고 있으면 저 그래프들을 나타낼 수 있다.

 

그리고 그래프를 추가하면서 고려해야 할 부분이 있다.

 

새로 들어온 초록색 직선

만약에 다음 그래프와 같이 새로 들어온 초록색 직선이 있다.

기존의 그래프들이 교차했던 부분의  x좌표인 s2보다 더 앞에서 만났다. 이것이 의미하는 바는 가장 마지막 부분의 빨간색 부분은 현재 새로 들어온 초록색 그래프보다 큰 값을 가지고 있고, 항상 최솟값을 가지지 않음을 알 수 있다.

즉, 따라서 위의 그래프는

 

변경된 그래프

이런 형식으로 변경되어야 할 것이다. 이번 경우에는 가장 마지막의 그래프보다 앞에 들어왔다고 예를 들었는데,

알고리즘은, 새로들어온 직선이 스택인경우에는 top, 벡터인 경우에는 back에 있는 그래프의 시작점보다 교점이 앞에 있을때, 그 저장하고 있는 그래프를 pop(), pop_back()하고, 또 반복하면서 si보다 앞에 있을때까지 반복한다고 생각하면 된다.

 

자 그럼 빨간색 부분의 그래프를 이런 방식으로 갖고 있다고 가정하자.

이제 어떻게 x ( a[i] )를 사용해서 함숫값을 바로 구할 수 있을까?

 

여기서는 이분 탐색을 한다.

구간을 정해도 되고 그래프의 index를 정해서 해도 된다.

이 코드에서는 그래프를 vector에 저장해놨기 때문에 원소에 바로 접근할 수 있다.

 

예를 들어 [s0, s1)의 범위에 있다면 [0]인 것처럼.. 

 

이제 주어진 x를 사용해서 구해보자.

매 반복마다 x의 좌표가 a[i]로 주어진다. 이제 이 x를 사용해서 어떤 직선에 접근해서 a, b를 사용할 것인지 구해야 한다.

 

각 그래프에서 s가 나타내는 것은 그래프가 시작하는 하한을 나타낸다.

따라서 이분 매칭을 할 때, x가 현재 mid(mid = (l+r)/2)가 나타내는 s보다 큰 경우, 몇 번째 직선인지 mid에 넣어두고

x과 더 가까운 s를 찾기 위해 left = mid+1로 수정해야 한다.

이 이유는 아까도 말했듯이 s가 하한 값이기 때문에 mid번째 직선보다 클 수는 있지만 그게 가장 가까운 직선인지는 장담할 수 없기 때문이다.

 

이렇게 하면 모든 i에 대해서(O(n)) 이분 탐색을 실행하니 O(logn) 전체 시간 복잡도는 O(nlogn)이 된다.

 

저도 공부할 때 이해가 잘 안돼서 코드를 들여다보니 이해가 바로 되었습니다.

이해하기 쉽게 구현했으니 아마도 코드를 보시면 이해가 잘될 거라 생각합니다.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX = 100000;

//f(x) = ax + b
struct Line {
	long long a, b;
	double s;

	Line(long long a_, long long b_, double s_ = 0) :a(a_), b(b_), s(s_) {}
};

double cross(const Line &f, const Line &g)
{
	//f(x)는 같으니까,
	//f.ax + f.b = g.ax + g.b이고 x를 좌변으로, 나머지를 우변으로 하면,
	// x= (g.b - f.b) / (f.a - g.a)
	return (g.b - f.b) / (f.a - g.a);
}

int a[MAX], b[MAX], n;
vector<Line> s;
long long dp[MAX];

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);

	for (int i = 0; i < n; ++i)
		scanf("%d", &b[i]);

	//1번부터, 0번은 0임
	for (int i = 1; i < n; ++i)
	{
		Line g(b[i - 1], dp[i - 1]);	//(a,b)

		while (s.size() >= 1)
		{
			//top과 교점을 구해봄
			g.s = cross(g, s.back());
			
			if (g.s < s.back().s)
				s.pop_back();	//g가 top보다 밑에 있으므로 top은 안 봐도 됨.
			else
				break;	//
		}
		s.push_back(g);

		long long x = a[i];
		int fpos = 0;

		int left = 0, right = s.size()-1;
		while (left <= right)
		{
			int mid = (left + right) / 2;
			if (s[mid].s < x) {
				fpos = mid;
				left = mid + 1;
			}
			else
				right = mid - 1;
		}
		
		dp[i] = s[fpos].a*x + s[fpos].b;

	}
	printf("%lld\n", dp[n - 1]);
	return 0;
}

 

6. 실행 결과 

 

 

댓글, 지적 언제든지 환영입니다. :-)