백준 14719 빗물 c++ (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/14719

14719번: 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

힌트

힌트 1:

힌트 2:

힌트 3:

알고리즘 분류

• 구현
• 시뮬레이션

풀이

구현, 시뮬레이션으로 분류되어 있고, 본인은 투 포인터를 이용해서 풀었다.

언뜻 보면 스택이 떠오르는 문제이지만, 조금만 생각해 보면 스택을 이용해서 풀긴 어려울 거 같다는 생각이 들 것이다.

바로 쉽게 풀이가 떠올랐다면, 아마 해당 풀이에 대한 반례가 많이 나올 것이다.

내 얘기다..

왼쪽 가장 큰 기둥의 인덱스를 left

오른쪽 가장 큰 기둥의 인덱스를 right라고 하자.

여기서 오른쪽 가장 큰 기둥이란, left의 높이와 같거나 더 높은 기둥을 말하며,

오른쪽 기둥을 찾았을 시, left에서 right사이에 있는 공간들을 모두 더해주면 된다.

이 부분은 딱히 고려할 게 없으며 left가 본인보다 작은 기둥들을 만날 때, input[left]-input[i]만큼씩 더해주며 sum을 더해나가다가, left가 본인과 같거나 높은 기둥인 right를 만나게 되면 sum을 최종 결과인 answer에 더해주고, left를 다시 right로 갱신하면 된다.

 

이제 고려해야 할 점은 다음과 같다.

그래프의 맨 왼쪽과 맨 오른쪽 벽은 뚫려있기 때문에, 그래프 내에서 높이를 입력으로 주어진 기둥 사이에만 물이 고일 수 있다.

위의 left right를 이용한 로직으로는 6 2 4 1 3 3 같은 경우 left보다 큰 기둥인 right를 만나지 못하기 때문에 sum이 0이다.

이러한 경우에는 어쩔 수 없이 사이에 물이 고이는 2 부분이나, 1부분을 직접 찾아줘야 하는데,

right 기둥을 맨 오른쪽 기둥인 3으로 잡고, left기둥인 6 사이에 있는 값들을 차례대로 비교해줬다.

6 2 4 1 3 3

right 왼쪽의 3은 right인 3과 같으므로 물이 고이지 않는다.

right를 왼쪽의 3으로 땡긴다.

 

6 2 4 1 3 3

right 왼쪽의 1은 right인 3보다 작으므로 물이 2만큼 고인다.

right는 냅두고 그 다음을 검사한다.

 

6 2 4 1 3 3

4는 right인 3보다 크므로 물이 고이지 않는다.

right를 4로 땡긴다.

 

6 2 4 1 3 3

2는 right인 4보다 작으므로 물이 2만큼 고인다.

더 이상 검사할 영역이 없기 때문에 sum은 4로 종료.

 

즉, 본인은 아직 검사하지 않은 가장 큰 왼쪽 기둥이 본인보다 크거나 같은 기둥을 만난 경우와, 만나지 못한 경우로 나누어서 풀었고, 시간 복잡도는 O(N)인 풀이이다.

 

사용 반례

100 18
28 100 43 33 37 100 87 15 52 35 54 86 60 24 99 56 4 40

답 : 602

 

코드

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int h, w;
	cin >> h >> w;
	int input[501];
	for (int i = 1; i <= w; i++) {
		cin >> input[i];
	}
	int left = 1;
	int answer = 0;
	int sum = 0;
	int right = 2;
	for (; right <= w; right++) {
		//크거나 같은 기둥 만났을 때
		if (input[left] <= input[right]) {
			answer += sum;
			left = right;
			sum = 0;
		}
		//작은 기둥 만났을 때
		else {
			sum += input[left] - input[right];
		}
	}
	
	right--;
	sum = 0;
	while (left < right) {
		for (int i = right - 1; i >= left; i--) {
        //right기둥보다 높이가 작은 경우 물이 고인다.
			if (input[i] < input[right]) {
				sum += input[right] - input[i];
			}
            //아닌 경우 right기둥 땡기기(중복 계산 대응)
			else {
				right = i;
				break;
			}
		}
	}
	answer += sum;
	cout << answer;

	return 0;
}