[BAEKJOON] 14719번 빗물

https://www.acmicpc.net/problem/14719

문제조건

1. 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. 
2. 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
3. 고이는 빗물의 총량을 출력

접근방법

 

정해진 알고리즘을 이용해서 푸는게 아니라, 내가 좋아하는 조건에 맞게만 풀면 되는 구현문제이다.

풀이법이 여러개가 떠올랐지만, 나는 블록들중 가장 높은 높이에서 부터 시작해서 아래로 스캔하는 방식을 선택했고, 한번 빗물을 채웠으면 더 이상 채울필요가 없으므로, visited배열을 통해서 이미 빗물이 고였음을 체크해줬다.

가장 중요한 빗물이 채워질 조건은 양 옆을 감싸는 블록이 적어도 2개이상은 있어야한다는것이다.

 

소스코드

#include <iostream>
#include <vector>
#define MAX 501
using namespace std;

int H, W;
int bar[MAX];
int high, res;
bool visited[MAX];

int main() {
	// 세로, 가로
	cin >> H >> W;
	for (int i = 0; i < W; i++) {
		cin >> bar[i];
		high = max(high, bar[i]);
	}
	// 위에서 부터 내려오고, 이미 체크된 구간은 다시 계산하지않음
	for (int h = high; h > 0; h--) {
		vector<int> v;
		for (int i = 0; i < W; i++) {
			if (h <= bar[i]) v.push_back(i);

		}
		if (v.size() >= 2) {
			for (int i = 0; i < v.size() - 1; i++) {
				for (int j = v[i]; j <= v[i + 1]; j++) {
					if (h - bar[j] < 0 || visited[j] == true) continue;
					res += h - bar[j];
					visited[j] = true;
				}
			}
		}
	}
	cout << res;
}

 

40분 가량 소요되었다,,, 구현 문제는 좀 더 빨리풀어보자