[BOJ/C++] 13263. 나무 자르기

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

13263번: 나무 자르기

 

1. 설명

나무를 자를 때마다 전기톱을 충전해야 합니다.

$i$번째 나무의 높이는 $a_i$이고,

전기톱을 충전하는 비용은 완전히 자른 (높이가 0인) 나무 중 가장 높은 번호를 $j$라고 할 때 $b_j$입니다.

이 때 모든 나무를 자르기 위한 총 충전 비용의 최솟값을 구해야 합니다.

$a_1 = 1 , b_n = 0$이 보장되며, $a_i < a_{i+1} , b_i > b_{i+1}$입니다.

 

2. 풀이

Convex Hull Trick을 배우고 풀어본 문제입니다.

$b_n = 0$이 보장되므로, $n$번째 나무를 완전히 자르는 비용을 묻는 문제라고 해석할 수 있습니다.

이 이후로는 충전 비용이 0이 되어 모든 나무를 추가 비용은 없이 자를 수 있기 때문입니다.

 

$i$번째 나무를 완전히 자르는 데 드는 비용은 $a_i \times b_j$입니다.

$i$번째 나무를 자르는 데 드는 최소 비용을 $D_i$라고 하면,

$j < i$인 $j$번째 나무를 완전히 자른 후 $i$번째 나무를 자를 때 드는 비용이 최소가 되는 $j$를 찾아야 하니

$D_i = \min_{j < i} (D_j + a_i \times b_j)$ 가 됩니다.

$N \le 100000$이므로 $O(N^2)$은 시간 초과가 발생합니다.

 

$a_i$를 $x$로 치환하면 직선의 기울기는 $b_j$, $y$절편은 $D_j$가 됩니다.

$b_j$가 $j$에 증가함에 따라 감소하므로, CHT를 적용하여 $O(n \log n)$ 안에 구할 수 있습니다.

 

여기서 $a_i$가 $i$가 증가함에 따라 증가하므로, $O(n)$에 구할 수도 있습니다.

 

3. 코드

$O(n \log n)$

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

using namespace std;

typedef long long ll;

ll N, A[100001], B[100001], d[100001], ans;

struct line
{
	ll a, b;
	double s = 0;

	line(ll a, ll b, double s) : a(a), b(b), s(s) {}

	bool operator<(const line& l) const
	{
		return s < l.s;
	}
};

vector<line> v;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];

	v.emplace_back(B[0], 0, 0); //D[i] when j = 0 : y = B[0] * A[i]

	for (int i = 1; i < N; i++)
	{
		line current(0, 0, A[i]); //y = A[i]
		line L = *(upper_bound(v.begin(), v.end(), current) - 1); //find the mininum line when x = A[i]

		d[i] = L.a * A[i] + L.b;

		line nxt(B[i], d[i], 0); //i-th line, based on d[i]
		double crossPoint = 0;

		while (v.size())
		{
			line prv = v.back();
			crossPoint = (double)(prv.b - nxt.b) / (nxt.a - prv.a); //nxt.a - prv.a should not be 0 => B[i] must be unique.

			if (crossPoint <= prv.s) v.pop_back(); //nxt line would result smaller value in [crossPoint, prv.s]. remove prv.
			else break;
		}

		nxt.s = crossPoint;
		v.push_back(nxt);
	}

	cout << d[N - 1];
	return 0;
}

 

$O(n)$

정작 제출하니까 시간이 크게 감소하진 않았습니다. 코드를 잘못 짰나?

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll N, A[100001], B[100001], d[100001], ans, pos, last;

struct line
{
	ll a, b;
	double s = 0;

	line(ll a = 0, ll b = 0, double s = 0) : a(a), b(b), s(s) {}

	bool operator<(const line& l) const
	{
		return s < l.s;
	}
};

line v[100001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];

	v[0] = line(B[0], 0, 0);
	last = 1;

	for (int i = 1; i < N; i++)
	{
		line current(0, 0, A[i]);
		while (last > pos + 1 && v[pos + 1].s < A[i]) pos++;

		line& L = v[pos];
		d[i] = L.a * A[i] + L.b;

		line nxt(B[i], d[i], 0);
		double crossPoint = 0;

		while (last > 0)
		{
			line prv = v[last - 1];
			crossPoint = (double)(prv.b - nxt.b) / (nxt.a - prv.a);

			if (crossPoint <= prv.s) last--;
			else break;
		}

		nxt.s = crossPoint;
        if (last <= pos) pos = last - 1; //current line was removed
		v[last++] = nxt;
	}

	cout << d[N - 1];
	return 0;
}