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

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

14719번: 빗물

문제

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

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

 

간단한 시물레이션 문제이다.

높이가 가장 큰 블록을 X라고 하면

왼쪽끝에서부터 X까지 빗물의 양 + 오른쪽 끝에서부터 X까지 빗물의 양을 더하는 방식으로 쉽게 구현할 수 있다.

나는 재귀의 형태로 구현하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define endl '\n'

using namespace std;

int H, W, height, heightIndex;
vector<int> rain;

int left(int index, int prev){
    if(index == heightIndex) return 0;
    int ret = 0;
    if(prev <= rain[index]) prev = rain[index];
    return ret += left(index+1, prev) + prev - rain[index];
}

int right(int index, int prev){
    if(index == heightIndex) return 0;
    int ret = 0;
    if(rain[index] >= prev) prev = rain[index];
    return ret += right(index-1, prev) + prev - rain[index];
}


void input(){
    cin >> H >> W;
    rain = vector<int>(W+1, 0);

    for(int i=1;i<=W;i++) {
        cin >> rain[i];
        if(height <= rain[i]){
            height = rain[i];
            heightIndex = i;
        }
    }
    cout << left(1, 0) + right(W, 0) << endl;
}

int main(){
    fastio; 
    input();

    return 0;
}