골드에그

1. 문제요약

www.acmicpc.net/problem/13263

높이가 a 인 나무 n 개를 전기톱을 이용해서 모든 나무를 완전히 자르려고 한다.

모든 나무를 완전히 자르는데 필요한 충전 비용의 최솟값을 구하는 프로그램을 작성하라.

룰은 다음과 같다.

① 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 쓰고 난 뒤에는 바로 충전해야 한다.

② 완전히 잘려진 나무가 없다면 전기톱은 충전할 수 없으며 높이가 0 이 되어버린 나무들 번호 중 최대값의 충전비용을 사용한다.

③ A 배열은 각 나무들의 높이이고 B 배열은 전기톱의 충전비용이다.

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

2. 문제예제

3. 팩트추출

Fact 1 : 문제지문에서 Bn 은 0 이라고 명시하고 있다. Bn 나무의 높이를 0 으로 만들 수 있는 최소 비용을 구할 수 있다면 나머지 나무들은 0 의 비용으로 모두 자를 수 있다. 즉, 문제가 "모든 나무를 완전히 자르는데 필요한 최소 비용" 에서 "Bn 나무의 높이를 0 으로 만들 수 있는 최소 비용" 으로 바뀐다.

Fact 2 : 전기톱을 사용해서 나무의 높이를 한 칸씩 줄일 때마다 충전해야 된다. 이 때 나무의 높이가 0 인 것이 하나라도 있어야 최소한 그 나무의 충전 비용으로 모든 나무를 완전히 자를 수 있다. 문제지문에서 A1 = 1 이고 A 배열은 단조증가배열인 점을 감안할 때, 첫 번째 나무를 먼저 베어야 게임 시작이 가능하다.

Fact 3 : 최소 비용을 구하는 것이기에 한 나무를 베기로 정했으면 중간에 다른 나무를 벨 필요는 없다.

Fact 4 : 위 사실들을 기반으로 문제를 정리하면 다음과 같다.

1번부터 N번까지의 나무가 있었을 때 1번부터 베기 시작해서 N번까지 베는 최소비용을 찾는다.

문제풀이 부분경로는 순차적이며 중간 경로를 건너 뛸 수 있다는 특징을 가지고 있다. 예를 들어 1번 2번 3번 … N번까지 차례대로 베거나, 1번에서 N번으로 바로 벨 수 있다.

4. 문제풀이(수동)

dp[i] : i 번째 나무를 높이 1로 만드는데 필요한 최소비용

a[i] : i 번째 나무 높이 , b[j] : j 번째 나무 충전비용이라고 할 때,

점화식은 dp[i] = min(1<j<i) dp[j] + a[i]b[j] 와 같다. 이 때 i 는 1부터 N까지이다.

다음은 예제 입력 2번을 기준으로 수동풀이이다.

dp[0] = 0

dp[1] = dp[0] + a[1]b[0] = 0 + 2*6 = 12

dp[2] = dp[0] + a[2]b[0] = 0 + 3*6 = 18

        = dp[1] + a[2]b[1] = 12 + 3*5 = 27

dp[3] = dp[0] + a[3]b[0] = 0 + 10*6 = 60

        = dp[1] + a[3]b[1] = 12 + 10*5 = 62

        = dp[2] + a[3]b[2] = 18 + 10*4 = 58

dp[4] = dp[0] + a[4]b[0] = 0 + 20*6 = 120

        = dp[1] + a[4]b[1] = 12 + 20*5 = 112

        = dp[2] + a[4]b[2] = 18 + 20*4 = 98

        = dp[3] + a[4]b[3] = 58 + 20*3 = 118

dp[5] = dp[0] + a[5]b[0] = 0 + 30*6 = 180     ---> ①

        = dp[1] + a[5]b[1] = 12 + 30*5 = 162     ---> ②

        = dp[2] + a[5]b[2] = 18 + 30*4 = 138     ---> ③

        = dp[3] + a[5]b[3] = 58 + 30*3 = 148     ---> ④

        = dp[4] + a[5]b[4] = 98 + 30*2 = 158     ---> ⑤

따라서 정답은 138 이다. 계산은 15번 소요되었다.

5. 문제전략

위 수동풀이처럼 순수 DP(점화식)로 푼다면, O({N*(N-1)}/2) 복잡도가 발생한다.

문제에서 N 이 100,000 이기 때문에 시간 제한(2초) 이내에 풀 수 없다. 다른 전략이 필요하다.

Solving Strategy Item 1 :

dp[i] = min(1<j<i) dp[j] + a[i]b[j] 점화식에서 변화하지 않는 부분 a[i] 를 이용한다.

a[i] 부분을 x 로 치환하면 y = bx+c 꼴 일차방정식으로 표현할 수 있는데

a 는 단조증가 b 는 단조감소 이기 때문에 마치 볼록한 껍질 형태의 그래프들로 표현할 수 있다.

convex hull 이라고 부른다. 예제 입력 2번을 실제 그래프로 표시해보자.

4번 문제풀이(수동) 을 자세히 보면 ① ② ③ ④ ⑤ 번 함수들이 계속 반복되는데 이 함수들을 그래프로 표시하면 위 그래프와 같다. 여기서 특징점들이 보인다.

파랑색 함수는 비교대상이 아니라는 점이다. 녹색 함수와 빨간 함수들만 보면 어느 X 값이라도 최소값을 확인할 수 있다.

일차함수이고 기울기가 낮아지는 함수들이다보니, 두 함수의 교점 X 좌표들을 비교만 해보아도 제외 대상을 가려낼 수 있다. 다시 말해 A 함수와 B 함수의 교점보다 B 함수와 C 함수의 교점이 낮다면 B 함수는 볼 필요 없는 것이다.

필요 없는 함수들을 제외하면서 그래프들의 교점들을 모아 두었다가 그 교점들과 A[i] 즉 x 값을 비교한다. x 값이 커질 때의 함수를 찾으면 x 값을 대입하여 y 값을 구할 수 있다.

Solving Strategy Item 2 :

그래프의 교점들과 비교할 때 이분탐색을 이용하면 O(NlogN) 시간복잡도까지 줄일 수 있다.

Solving Strategy Item 1번을 통해 교점들 x 좌표가 오름차순으로 정렬이 되기 때문에 순차적으로 값을 찾기 보다는 이분탐색으로 찾는 것이 훨씬 빠르다.

6. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 100000;

// 일차 함수 표현 : f(x) = ax+b
struct Line {
	long long a, b;
	double cross_x;

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

// 두 함수의 교차점 
double cross(const Line& f, const Line& g)
{
	// f 를 f.ax+f.b 라 하고, g 를 g.ax + g.b 라 할 때 x 를 왼쪽에 남겨두고 이항하면,
	return (g.b - f.b) / (f.a - g.a);
}

// 이분 탐색
int binary_search(vector<Line>& line, long long key)
{
	int position = 0;
	int left = 0, right = line.size() - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (line[mid].cross_x < key) {
			position = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	return position;
}

long long dp[MAX];

int main()
{
	// 입력 예제 2번
	int n = 6; // N 나무
	vector<int> a = { 1,2,3,10,20,30 }; // 나무 높이
	vector<int> b = { 6,5,4,3,2,0 }; // 충전 비용

	vector<Line> line_stack;

	// dp[0] 은 항상 0 이므로, 1부터 시작
	for (int i = 1; i < n; ++i)
	{
		// 나무가 N 개이면, N-1 개의 점화식이 존재함
		Line g(b[i - 1], dp[i - 1]);    // y = ax+b 에서 차례대로 (a, b)

		while (line_stack.size() >= 1)
		{
			g.cross_x = cross(g, line_stack.back());

			if (g.cross_x < line_stack.back().cross_x) // 교점을 통해 비교. 위에 있는 함수는 버림.
				line_stack.pop_back();
			else
				break;
		}
		line_stack.push_back(g);

		int x_position = 0;
		x_position = binary_search(line_stack, a[i]);
		// y 값 계산
		dp[i] = line_stack[x_position].a * a[i] + line_stack[x_position].b;

	}
	cout << dp[n - 1] << endl;
	return 0;
}