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

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

14719번: 빗물

1. 주의할 점

- 해당 블록을 기준으로 오른쪽과 왼쪽을 살핀다

 

2. 구현

- 해당 블록을 I를 기준으로 0~I-1과 왼쪽에 위치한 I+1~Col블록을 검사하며 왼쪽 블록중 가장 높은 블록과 오른쪽 블록중 가장 높은 블록을 구한다

- 위에서 구한 높이중 작은 높이를 현재 높이만큼 빼면 현재 블록에 최대 얼마의 빗물을 담을 수 있는지 구할 수 있다

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[502];
int row, col;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int result = 0, r, l;
	cin >> row >> col;
	for (int i = 1; i <= col; i++)
		cin >> arr[i];
	for (int i = 2; i < col; i++) {
		r = l = arr[i];
		for (int j = 1; j < i; j++)
			l = max(l, arr[j]);
		for (int j = i + 1; j <= col; j++)
			r = max(r, arr[j]);
		result += (min(r, l) - arr[i]);
	}
	cout << result;
	return 0;
}