BOJ 14719. 빗물

🙇‍♀️[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

구현, 시뮬레이션

제출 일자

2024년 2월 18일 18:44:20

문제 설명

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

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

🚀풀이

물이 차는 정도를 알기 위해서 해당 위치를 기준으로 왼쪽, 오른쪽을 탐색해야한다.

왼쪽으로 탐색할 떄 자기보다 높은 탑이 얼마인지, 오른쪽으로 탐색할 때 자기 보다 높은 탑이 얼마인지 구한다.

이 떄 자신보다 높은 탑이 없다면 빗물이 고일 수 없다.

자신보다 높은 탑이 있을 경우 왼쪽 오른 쪽 둘 다 높아야한다.

둘 다 높을 때 그 중 낮은 탑을 기준으로 빗물이 고인다.

이 때 고인 빗물의 양은 낮은 탑 높이에서 자신의 탑 높이의 차이이다.

이걸 이용해서 코드를 구현하면 아래와 같다.

int h, w;
vector<int> rains;
void solve()
{
	cin >> h >> w;
	rains = vector<int>(w);
	for (int i = 0; i < w; ++i)
	{
		cin >> rains[i];
	}

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

		for (int j = w - 1; j > i; --j)
		{
			right = max(right, rains[j]);
		}

		res += max(0, min(left, right) - rains[i]);
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int h, w;
vector<int> rains;
void solve()
{
	cin >> h >> w;
	rains = vector<int>(w);
	for (int i = 0; i < w; ++i)
	{
		cin >> rains[i];
	}

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

		for (int j = w - 1; j > i; --j)
		{
			right = max(right, rains[j]);
		}

		res += max(0, min(left, right) - rains[i]);
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}