BOJ 8987 수족관 3

문제 링크입니다.

문제 요약

히스토그램의 위아래를 뒤집어 물을 가득 채웁니다. 바닥에 $K$개의 구멍을 뚫어 빼낼 수 있는 최대 물의 양을 구하세요.

풀이

적당히 구멍을 하나 뚫어봅시다. 위부터 물이 빠지다가, 제일 높은 바닥을 기점으로 물이 여러 구간으로 쪼개져서, 구멍이 있는 쪽만 물이 더 빠지고 나머지 구간은 거기서 멈추겠죠.

한 구간 안의 제일 높은 바닥 기준으로 왼쪽/오른쪽의 제일 높은 바닥을 연결하는 식으로 구간이 나뉘는 기점을 순서대로 이진 트리로 만들 수 있습니다. 이러한 구조는 데카르트 트리라는 이름으로 알려져 있습니다. 이 트리 상의 한 정점은 그 정점에 해당하는 바닥이 제일 높은 바닥인 가장 큰 구간을 표현합니다. 이때 해당 구간의 천장은 원본 히스토그램의 천장이 아니라, 해당 정점의 부모 정점의 바닥 높이입니다. 이렇게 하면 정확히 해당 구간 안에 구멍을 뚫어야만 빠지는 모든 물을 고려할 수 있게 됩니다.

전체 구간 안에서 구멍 하나를 뚫고 싶다고 해 봅시다. 구간 안의 어느 바닥에 구멍을 뚫든 제일 높은 바닥 위로 차 있는 물은 다 빠집니다. 그러니 왼쪽 구간과 오른쪽 구간만 각각 고려했을 때 더 물이 많이 빠지는 쪽에 구멍을 뚫는 게 좋겠죠. 이걸 모든 구간에 대해 생각해 줄 수 있고, 그러면 결국 최적으로 구멍을 뚫었을 때 각 구간의 위에 쌓인 물이 어느 바닥에 구멍을 뚫었을 때 빠지게 되는지, 그리고 각 바닥에 구멍을 뚫었을 때 얼마의 물이 빠지게 될지가 그리디하게 결정됩니다.

이제 이 값들을 정렬해서 제일 큰 거 $K$개 뽑아주면 됩니다. 데카르트 트리는 ${\cal O}(N)$에도 구할 수 있긴 한데, 그냥 적당히 ${\cal O}(N \lg N)$ RMQ로 만들어도 충분합니다. 그리고 어차피 ${\cal O}(K \lg K)$ 짜리 정렬해야 되는데 $K$가 ${\cal O}(N)$이에요. 총 시간 복잡도는 ${\cal O}(N \lg N)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

ll h[151515], x[151515], mh[18][151515];
priority_queue<ll> pq;

int rmq(int l, int r){
	int bit = 31-__builtin_clz(r-l+1);
	int L = mh[bit][l], R = mh[bit][r-(1<<bit)+1];
	return h[L] < h[R] ? L : R;
}

ll solve(int l, int r, ll ph = 0){
	if(l > r) return 0;
	int mid = rmq(l, r);
	ll ql = solve(l, mid-1, h[mid]), qr = solve(mid+1, r, h[mid]);
	if(ql > qr) swap(ql, qr);
	pq.push(ql); return qr+(h[mid]-ph)*(x[r+1]-x[l]);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; n >>= 1;
	for(int i = 1; i <= n; i++) cin >> x[i] >> h[i] >> x[i] >> h[i], mh[0][i] = i;
	for(int bit = 1; (1<<bit) <= n; bit++) for(int i = 1; i+(1<<bit)-1 <= n; i++){int L = mh[bit-1][i], R = mh[bit-1][i+(1<<bit-1)]; mh[bit][i] = (h[L]<h[R]?L:R);}
	pq.push(solve(1, n)); ll k, ans = 0; cin >> k; while(k--) ans += pq.top(), pq.pop(); cout << ans;
}