BOJ 8982 수족관 1

사용한 알고리즘

구현

알고리즘 설명

먼저 수족관 포인트 정보를 point에 저장하는데 짝수 인덱스 값만 봐도 이 틀을 알아 낼 수 있다.
이 뒤에 수족관에 있는 모든 물을 미리 결과 값에 저장한다.
구멍을 모두 입력받고 오름차순 정렬한다.
구멍의 위치는 i인덱스로, 수족관 좌표는 j인덱스로 찾아간다.
먼저 구멍위치가 있는 수족관 좌표를 찾는다.
이 뒤에 현재 위치의 물을 빼주고 좌우의 물을 빼주는 형태로 진행한다.
각 수조관 좌표가 가지는 물의 높이를 저장하는데, 초기가 0이며 점점 내려가는 형태로 저장한다.
이를 통해 모든 구멍으로 부터 물을 제외하고 남은 결과 값을 출력한다.

풀이

// baekjoon 8982 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N=2501;

int N, K, a, b, c, d;
int height[MAX_N];
ll ret;
P point[MAX_N], hole[MAX_N];

int main() {
	scanf("%d", &N);
// 수족관 좌표의 짝수만 저장한다. 수족관 높이의 변화 지점만 저장하기 위함
	for (int i=0; i<N; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (i%2==0) point[i/2]={u,v};
	}
	N/=2;
// 수족관에 모든 물을 결과에 더한다.
	for (int i=1; i<N; i++)
		ret += point[i].second*(point[i].first - point[i-1].first);

	scanf("%d", &K);
	for (int i=0; i<K; i++) {
		scanf("%d%d%d%d", &a,&b,&c,&d);
		hole[i]={a,b};
	}
	sort(hole, hole+K);

// 물빼는 작업을 진행한다.
	for (int i=0; i<K; i++) {
		int j=1;
// hole(i)가 발생하는 수족관 좌표(j-1) ~ j 인 j 값을 찾는다.
		while (!(point[j].second == hole[i].second && point[j-1].first <= hole[i].first && hole[i].first <= point[j].first)) j++;
// 수족관의 물이 이미 다 빠진경우 물 빼는 작업을 하지 않는다.
		if (height[j] == point[j].second) continue;

// 현재 구멍이 있는 곳에 물을 빼준다.
		ret -= 1LL*(hole[i].second - height[j])*(point[j].first - point[j-1].first);
// j번째 수족관 좌표 부분의 높이를 물을 뺀 만큼 적는다.
		height[j] = hole[i].second;

		int lh = hole[i].second;
		int lj = j-1;
// 왼쪽 부분의 물을 빼기 시작한다.
		while (lj>=1) {
// 높이가 현재보다 작은 부분만 물이 빠진다. 높이가 점점 올라가면 그 이후는 그 높이에 따른다.
			lh = min(lh, point[lj].second);
// 이미 물이 빠진 경우, 또는 높이가 0이라 더이상 빼지 못하는 경우 나감
			if (!lh || height[lj] == lh) break;
// 물빼는 작업을 하고 높이를 업데이트함
			ret -= 1LL*(lh - height[lj])*(point[lj].first - point[lj-1].first);
			height[lj] = lh;
			lj--;
		}

// 우측도 좌측가 같은 알고리즘을 적용한다.
		int rh = hole[i].second; 
		int rj = j+1;
		while (rj < N) {
			rh = min(rh, point[rj].second);
			if (!rh || height[rj] == rh) break;
			ret -= 1LL*(rh - height[rj])*(point[rj].first - point[rj-1].first);
			height[rj] = rh;
			rj++;
		}
	}
// 결과를 출력한다.
	printf("%lld\n", ret);
	return 0;
}