# 14719. 빗물

관련 알고리즘 : 구현, 시뮬레이션

 

문제 링크 : https://www.acmicpc.net/problem/14719

14719번: 빗물

 

---

해결 과정

 

2차원 세계의 블록이 있고, 세로 길이 H(H>=1)와 가로 길이 W(W<=500)가 주어진다. 

바닥은 항상 막혀 있다고 하였으므로 양 옆이 한칸이라도 막혀있다면 빗물이 고일 수 있지만,

문제에서 제시한 예제 3을 보면 블록 높이가 0 0 0 2 0 일 때 고인 빗물이 0 이므로

가장 왼쪽과 가장 오른쪽 부분에는 벽이 존재하지 않아 빗물이 고일 수 없음을 알 수 있다.

즉,

양 극단의 경우

1. 블록이 존재 >> 블록 때문에 빗물이 고일 수 없음
2. 블록이 존재하지 않음 >> 양 극단은 바닥처럼 벽이 막혀 있지 않기 때문에 빗물이 고일 수 없음

이 2가지 경우가 존재하고, 어떤 경우에도 빗물이 고일 수 없다.

따라서, 가로가 1~W까지 존재한다고 할 때, 빗물은 2~(W-1) 부분에만 존재할 수 있다.

 

예시를 만들어 해결 과정을 생각해보자.

각 가로길이 n당 있는 블록의 높이를 h(n)이라 하면,

W7 X H6. 왼쪽부터 W1, W2, W3, W4, W5, W6, W7이라 가정

각 Wn(1<=n<=7) 에 있는 빗물이 고일 수 있는 최대높이 maxH(n)는

maxH(n) = min(Wn의 좌측 블록 h중 최대, Wn의 우측 블록 h 중 최대) 라고 할 수 있음을 알 수 있다.

그렇다면, 해당 Wn에 고인 빗물은 maxH(n) - h(n) ( maxH(n) >= h(n) )이라고 할 수 있다.

이를 위 예시에 적용해보면,

 

• W2에서 h(2) = 0. maxH(2) = 4 →  4-0 = 4
• W3에서 h(3) = 2. maxH(3) = 4 →  4-2 = 2
• W4에서 h(4) = 6. maxH(4) = 4 인데 h(4) > maxH(4) 이므로 0
• W5에서 h(5) = 1. maxH(5) = 5 →  5-1 = 4
• W6에서 h(6) = 3. maxH(5) = 5 →  5-3 = 2

사진 속 예시의 빗물 양과 일치함을 알 수 있다. 

---

C++ 코드

#include <iostream>
#include <algorithm>

#define MAX 501

using namespace std;


int h, w; // 세로길이 h, 가로길이 w
int height[MAX]; // 각 가로 당 블럭높이
int res = 0; // 총 빗물 양

void rain()
{
	int leftMax;
	int rightMax;

	for (int i = 2; i < w; i++)
	{
		leftMax = height[i];
		rightMax = height[i];

		for (int j = 1; j < i; j++) // 좌측 블록 최대높이 구하기
		{
			leftMax = max(leftMax, height[j]);
		}

		for (int j = i + 1; j <= w; j++)
		{
			rightMax = max(rightMax, height[j]); // 우측 블록 최대높이 구하기
		}

		res += ( min(leftMax, rightMax)-height[i] ); // 빗물 최대 높이 구하기
	}

	cout << res;

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> h >> w;
	for (int i = 1; i <= w; i++)
	{
		cin >> height[i];
	}

	rain();
	return 0;
}