[백준 BOJ14719] 빗물 (C++)

1. 제목

- 백준 14719 빗물

- BOJ 14719 빗물

문제 링크 : 14719번: 빗물 (acmicpc.net)

14719번: 빗물

---

2. 풀이 과정

 

왼쪽 블록을 기준점으로 시작해서 오른쪽으로 탐색을 시작하는데 매번 높이를 비교하며 현재 기준점이 되는 블록보다 높거나 같은 블록을 발견하면 기준점 블록을 해당 블록으로 갱신을 해줘요.

또한 매번 기준점 블록을 갱신하기 전 기준점 블록과 현재 탐색 중인 블록의 사이에 빈 곳이 존재한다면 기준점과 현재 블록의 높이 중 낮은 높이까지 빗물을 표시해 주어서 문제에서 요구하는 고인 빗물을 구할 수 있었어요.

빗물 체크를 할 때 탐색을 매번 기준점 블록이 바뀌기 전까지 탐색했던 곳을 또 탐색하는 낭비가 있기는 한데…. 너무 쉽게 풀려고 한 느낌이 있는 거 같아요.

---

3. 코드

#include <iostream>
#include <vector>

using namespace std;

// 세로 가로
int H, W;
// 맵
int map[501][501];
// 높이 저장 백터
vector<int> v;
// 정답 변수
int result;

void Marking(int startX, int endX)
{
	int height;
	if (v[startX] < v[endX])
		height = v[startX];
	else
		height = v[endX];


	for (int x = startX; x < endX; x++)
	{
		for (int y = 0; y < height; y++)
		{
			if (map[y][x] == 0)
			{
				result++;
				map[y][x] = 2;
			}
		}
	}
}

void Solution()
{
	int selectX = 0;
	for (int x = 1; x < W; x++)
	{
		Marking(selectX, x);

		// 현재 선택된 높이보다 더 높거나 같은 높이를 발견 했다면
		if (v[selectX] <= v[x])
			selectX = x;
	}
	cout << result << endl;
}

void Input()
{
	cin >> H >> W;

	for (int x = 0; x < W; x++)
	{
		int height;
		cin >> height;
		v.push_back(height);
		for (int y = 0; y < height; y++)
		{
			map[y][x] = 1;
		}
	}
}

int main()
{
	Input();
	Solution();
	return 0;
}