[백준][C++] 14719: 빗물

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

 

정말 오랜만에 문제를 풀어봤습니다. 모 회사의 라이브코딩 문제였다고 하는데 이정도 난이도로만 나와주면 참 좋겠습니다.

블록이 위 사진처럼 쌓여있고 비가 올때 블록 사이에 빗물이 고인다고 합니다. 이때 고이는 빗물의 총량을 구하는 것이 문제입니다.

풀이는 대략 아래와 같습니다.

• 맨 밑에서부터 한 칸씩 높이를 높이면서 빗물이 고일 수 있는지 체크함
• 빗물이 고이려면 적어도 그 높이에서 2칸 이상 블록이 채워져 있어야 함 (한쪽이 뚫려있으면 빗물이 새니까)
• 맨 왼쪽과 맨 오른쪽 인덱스를 구하고 그 줄의 총 블록 개수를 세서 계산
  • r-l+1-블록 수

#include <bits/stdc++.h>
using namespace std;

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

	int h, w;
	cin >> h >> w;
	
	vector<int> heights(w);
	for (auto& c : heights)
		cin >> c;

	int counter = 0;
	for (int i = 0; i < h; ++i) {
		int blocked = 0;
		int left=INT_MAX, right=INT_MIN;
		for (int j = 0; j < w; ++j) {
			if (heights[j] > i) {
				++blocked;
				left = min(left, j);
				right = max(right, j);
			}
		}

		if (blocked == 0)
			break;
		else if (blocked == w)
			continue;
		else {
			counter += (right - left + 1) - blocked;
		}
	}

	cout << counter << '\n';

	return 0;
}

h, w 조건이 널널하기 때문에 이러저러하게 풀어도 다 풀릴 것 같습니다