(문제 링크: 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 조건이 널널하기 때문에 이러저러하게 풀어도 다 풀릴 것 같습니다

반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 10830: 행렬 제곱  (0) 2020.10.30
[백준][C++] 1322: X와 K  (0) 2020.10.29
[백준][C++] 17419: 비트가 넘쳐흘러  (0) 2020.08.30
[백준][C++] 1083: 소트  (0) 2020.08.29
[백준][C++] 3300: 무어 기계  (0) 2020.08.28