[C++]백준14719번 빗물

오늘은 백준14719번 빗물 문제를 풀어보도록 하자.

구현, 시뮬레이션 문제로 작년 하반기 Nxx코딩테스트에 나온 문제이다. 당시 많이 버벅였던 문제였다. 지금 풀어보니 굉장히 단순한 문제였다..

문제는 다음과 같다.

                               [접근법]

  1. 기준 인덱스로 부터 왼쪽, 오른쪽을 탐색하여 가장 큰 값들을 저장해놓는다.

  2. 그 후 저장된 값 중 작은 값에서 기준 인덱스의 map 값을 빼주어 result에 누적합 해준다.
  
  3. 물론 기준 인덱스의 map 값이 저장된 값 중 작은 값보다 크면 continue하여 계산하지 않는다. (빗물이 고이지 않으므로)

                                     [코드]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int H, W, result = 0;//세로, 가로, 답
	int map[500];//전체 맵

	cin >> H >> W;

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

	for (int i = 1; i < W - 1; i++) {
		int l = 0, r = 0; // l은 기준에서 왼쪽, r은 기준에서 오른쪽

		for (int j = 0; j < i; j++) {
			l = max(map[j], l);
		}
		for (int j = i + 1; j < W; j++) {
			r = max(map[j], r);
		}
		
		if (map[i] > l || map[i] > r) {
			continue;
		}
		else {
			result += min(l, r) - map[i];
		}
	}
	cout << result << '\n';
	return 0;
}