빗물(백준 14719)

김인회·2021년 5월 21일

알고리즘

목록 보기

34/53

(출처) https://www.acmicpc.net/problem/14719

포인터 2개로 탐색해가면서 정답을 구하자

left, right 2개의 포인터를 만들고 최초에는 두 포인터 모두 맨 왼쪽의 블록을 가리키도록 한다.

이후 right 포인터를 하나씩 증가시켜가며 블록을 탐색하면서, 탐색 중에 빗물이 고일만한 위치가 확정된다면(left가 가리키는 블록보다 크거나 같은 right 블록이 나올 경우) 빗물의 양을 계산해서 정답에 더해준다.

빗물 위치가 확정되어 계산 과정이 진행됐다면 left와 right 사이에 있던 블록들은 이제 더 이상 확인할 필요가 없어지므로, left를 right 위치로 옮기고 다시 모든 블록을 확인할 때까지 탐색 로직을 반복한다.

이때 주의해야 할 예외상황은 right가 블록의 끝에 다다랐는데 끝에 있는 블록의 크기가 현재 left 블록의 크기보다 작을 때이다.

left-right 블록모양은 2가지

포인터 left와 right가 가리키고 있는 블록의 모양은 총 2가지 경우로 나누어진다.

left 블록의 높이가 right 블록의 높이보다 작거나 같은 경우

left 블록의 높이가 right 블록의 높이보다 큰 경우

전자의 경우, 빗물이 고인 크기가 확정되어 있는 블록모양으로 이후에 발견되는 블록들과는 상관없이 고인 빗물의 크기가 확정됐다고 볼 수 있다. 따라서 해당 모양이 발견된다면 곧바로 고인 빗물의 양을 계산을 해주면 된다.

하지만 후자 블록모양의 경우 빗물이 고여있는지 아닌지, 얼마만큼 고여있는지를 섣불리 단정 지을 수 없다. 이어지는 탐색과정에서 만나는 right 블록의 모양에 따라서 고인 빗물의 유무와 그 양이 계속 달라지기 때문이다.

따라서 현재 left-right가 가리키고 있는 블록이 후자의 모양인 경우에는, 빗물 계산을 진행하지 않고 계속해서 right 포인터를 늘려나가며 다음 블록의 모양을 확인해봐야 한다.

여기서 주의해야 할 것은 right가 전체 블록의 끝까지 다다라 탐색이 종료되었는데도 left-right 블록모양이 여전히 후자의 모양을 띄고 있는 경우다.

내가 생각하는 로직에서 빗물 계산은 오로지 1번 모양일 때에만 계산이 진행되었으므로 2번의 모양으로 탐색이 종료되어버리면 해당 블록모양에 고인 빗물의 양을 계산하지 않게 돼버린다.

따라서 탐색이 종료되었는데 left-right의 블록모양이 2번인 경우(right가 left보다 작은 경우) 추가적으로 빗물 계산을 진행해 주어야 한다.

해당 과정의 계산은 left-right가 가리키고 있는 블록을 좌우대칭으로 뒤집어 1번 모양으로 변형시킨 후 다시 한번 계산을 진행해 주는 식으로 구현하였다.

시간복잡도

해당 로직에서 계산이 가장 많이 일어나게되는 가장 최악의 경우는 블록 전체의 모양이 2번 형태를 띠고 있는 형태로, left가 블록의 가장 첫 번째 블록을 가리키고 있는 상황에서 right가 블록의 끝점까지 다다를 동안 left보다 큰 블록이 존재하지 않는 상황이다.

해당 경우는 결국 전체 블록을 처음부터 끝까지 2번 탐색하게 되는데 문제에서 주어지는 블록의 최대 크기는 500개라고 했으므로 결국 탐색 계산 회수는 많아봐야 1000번이다.

따라서 시간복잡도는 절대 걱정할 필요가 없다.

코드

#pragma warning (disable : 4996)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int left, vector<int>& blocks, bool is_reverse) {
	int ret = 0;
	int temp_ret = 0;
	int right = left;
	while (true) {
		int close_h = blocks[right];
		int open_h = blocks[left];
		if (right == blocks.size() - 1) {
			if (is_reverse) {
				ret += temp_ret;
				return ret;
			}
			if (open_h <= close_h) {
				ret += temp_ret;
				return ret;
			}
			else break;
		}
		if (left == right) {
			right++;
			continue;
		}
		if (open_h > close_h) {
			temp_ret += open_h - close_h;
			right++;
			continue;
		}
		else {
			ret += temp_ret;
			temp_ret = 0;
			left = right;
		}
	}
	reverse(blocks.begin() + left, blocks.end());
	ret += solution(left, blocks, true);
	return ret;
}

int main(){
	int h, w;
	cin >> h >> w;
	vector<int> blocks(w);
	for (int i = 0; i < w; i++) cin >> blocks[i];
	int ret = solution(0, blocks, false);
	cout << ret << "\n";
}