[BOJ] 14719번_빗물_구현 (C++)

[문제]

https://www.acmicpc.net/problem/14719

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

비는 고일만큼 충분히 올때, 빗물의 총량이 얼마인지 구하는 문제이다.

[사용 알고리즘]

구현

[풀이 핵심]

• 이 문제는 각 칸마다 빗물이 얼마나 쌓일 수 있는지 구해서 더하는 것이 가장 쉽게 해결할 수 있는 법이다.
• 입력 받은 값을 for문을 통해 순회하며 현재 값의 왼쪽, 오른쪽의 최대값을 구한다. 그 최대 값중 작은 값이 물이 고일 수 있는 최대 높이이며, 여기서 현재칸의 높이를 빼면 현재칸에 고일 수 있는 물의 양이 된다. 이 값들을 전부 더해주면 빗물의 총량이 된다.

[코드]

//boj14719번_빗물_구현

#include<iostream>

using namespace std;

int width[501];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int h, w;
	cin >> h >> w;

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

	int result = 0;

	for (int i = 1; i < w - 1; i++) {
		int left = width[i];
		int right = width[i];

		for (int j = 0; j < i; j++) {
			left = max(left, width[j]);
		}
		for (int j = i; j < w; j++) {
			right = max(right, width[j]);
		}

		result += min(left, right) - width[i];
	}

	cout << result;
}