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

문제 링크

14719번: 빗물

문제 요약

2차원 세계에 쌓여 있는 블록이 주어지고 비가 충분히 많이 올 때, 고일 수 있는 빗물의 총량을 출력한다.

접근 방법

간단한 구현 문제였습니다.

입력 받은 높이를 2차원 배열에 저장을 해준 다음에, 가장 아래 행부터 순서대로 검사를 해주면 됩니다. 맨 오른쪽 열부터 한 칸씩 이동하면서 현재 칸이 벽인지, 벽이 아닌지를 판정해주는 식으로 접근을 했습니다.

각 행의 최우측 열부터 이동하다가 최초로 벽을 만났다면, 그 이후로는 왼쪽은 벽으로 무조건 막혀있다고 생각할 수 있습니다. 그렇기 때문에 최초의 벽을 만난 이후로는 오른쪽으로 이동하면서 벽이 아닌 구간을 세주고, 벽을 만나는 순간 세주던 값을 결과에 더해주기만 하면 됩니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 501

using namespace std;

bool block[MAX][MAX];

int main(void)
{
	FASTIO;

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

	for (int i = 1; i <= w; i++)
	{
		int height;
		cin >> height;

		for (int j = 1; j <= height; j++)
			block[j][i] = true;
	}

	int res = 0;
	for (int i = 1; i <= h; i++)
	{
		int cnt = 0;
		bool flag = false;

		for (int j = 1; j <= w; j++)
		{
			if (!flag && block[i][j])
				flag = true;
			if (flag && !block[i][j])
				cnt++;
			if (flag && block[i][j])
				res += cnt, cnt = 0;
		}
	}

	cout << res << endl;
	return 0;
}