BOJ 14719 . 빗물

물이 고일 때 해당 인덱스 위치에서 좌,우의 벽이 현재 인덱스 벽 높이보다 낮으면 빗물이 고일 수가 없다.

첫 번째 테스트 케이스에서 맨 왼쪽은 3, 현재 인덱스는 0, 오른쪽 인덱스는 1이라고 가정할 때 현재 인덱스에 대한 높이가 제일 낮기에 빗물이 고일 수 있다. 여기서 얼마나 고일 지 어떻게 계산할 지가 관건이다.

현재 인덱스의 왼쪽에 존재하는 인덱스들의 벽 높이 중에서 최대값과, 오른쪽에 해당하는 최대값을 구하여 둘 중의 최소값을 구해서 그 값에 현재 인덱스에 해당하는 벽 높이를 빼면 물 높이를 구할 수가 있다.

예를 들어보자.

인덱스 1에 해당하는 벽의 높이는 0, 왼쪽에서 제일 큰 벽 높이는 3, 오른쪽에서는 4이다.

물이 고일때 3을 넘을 경우 물이 넘치기 때문에 여기서 최소값을 구해주어야 하는 것이다. 즉 여기서 3이 될테고, 3 - 0 = 3. 즉 1번 인덱스 위치에 물이 3만큼 고이게 된다.

이렇게 반복을 하면 되는데, 추가로 생각해주어야 할 점은 맨 왼쪽 벽과 오른쪽 벽은 끝과 끝이므로 해당 인덱스서 포함하지 않는게 좋다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int lmax(vector<int> vec, int idx)
{
	int m = 0;
	// i = 1
	for (int i = idx-1; i >=0; i--)
	{
		m = max(m, vec[i]);
	}
	return m;
}

int rmax(vector<int> vec, int idx)
{
	int m = 0;
	for (int i = idx + 1; i < vec.size(); i++)
	{
		m = max(m, vec[i]);
	}
	return m;
}


int main()
{
	int H, W;
	cin >> H>>W;
	vector<int> vec(W);

	for (int i = 0; i < W; i++)
	{
		cin >> vec[i];
	}

	int water = 0;
	int lx, rx,hv;
	for (int i = 0; i < vec.size(); i++)
	{
		lx = lmax(vec, i);
		rx = rmax(vec, i);
		hv = min(lx, rx);
		if (hv > vec[i]) {
			water += hv - vec[i];
		}
	}
	cout << water << endl;




	return 0;
}