백준 14719번 빗물

문제

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

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

입력

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

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

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

출력

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

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

 

 

규칙 찾기.

현재 위치에서 더해지는 개수는 어떤 규칙을 가지고 있는가?

자신 기준 왼쪽에서 최댓값과 오른쪽 최댓값 중에 작은 값과 자신의 차이만큼 빼줌 

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int h, w;

int arr[501];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> h >> w;

	for (int i = 1; i <= w; i++)
		cin >> arr[i];

	int ans = 0;
	for (int i = 2; i < w; i++)
	{
		int cur = arr[i];
		int max_left = 0;
		int max_right = 0;

		for (int j = i - 1; j >= 1; j--)
			if (max_left < arr[j])
				max_left = arr[j];
		for (int j = i + 1; j <= w; j++)
			if (max_right < arr[j])
				max_right = arr[j];


		int min_res = min(max_left, max_right);
		if (min_res - cur > 0)
			ans +=  min_res - cur;

	}
	cout << ans;



	
}