[백준] 14719-빗물(C++)

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

14719번: 빗물

 

평범한 구현문제입니다.

 

문제에서 준 조건은 2가지 입니다.

 

• 블록내부에 빈공간은 생기지 않는다.
• 바닥은 막혀있다 가정한다.

 

h와 w의 범위가 1 ~ 500 까지 임으로 단순 구현을 통해서 문제를 해결했습니다.  O(n^3)

 

 

500 x 500 각각의 좌표에서 빗물이 보관되는지 확인하여 구현했습니다.

쉬운문제이기 때문에 코드를 보시면 금방 이해하실겁니다.

 

 

정답코드입니다.

#include <iostream>
using namespace std;


int h = 0, w = 0;
int arr[501] = { 0, };
int result = 0;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> h >> w;
	for (int i = 1; i <= w; i++)
		cin >> arr[i];
	for (int i = 1; i <= h; i++) {
		for (int j = 2; j <= w - 1; j++) {
			if (arr[j] >= i) continue;

			bool leftt = false;
			bool rightt = false;
			//left identify
			for (int k = j - 1; k >= 1; k--) {
				if (arr[k] >= i)
				{
					leftt = true;
					break;
				}
			}
			//right identify
			for (int k = j + 1; k <= w; k++) {
				if (arr[k] >= i)
				{
					rightt = true;
					break;
				}
			}

			if (leftt == true && rightt == true)
				result++;
		}
	}

	cout << result << endl;

	return 0;
}