알고리즘/백준

[백준/c++] 14719번: 빗물

녕이 2022. 11. 15. 15:47
728x90

 

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

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

 

stack에 넣고 하는 걸로 생각했는데, 사실 더 간단하게 진행할 수 있다.

괜히 stack으로 하다가 헷갈려서 계속 실수했다.

양끝 블록은 웅덩이가 될 수 없기 때문에 1~w-2 블록들을 차례대로 하나씩 웅덩이가 될 수 있는지 체크해주면 된다.

양쪽에 웅덩이의 기둥이 뒬 수 있는 max left, right를 구하고 더 작은놈에서 현재 블록의 값을 빼주면 된다.

음수가 나올 수 있기 때문에 0보다 작다면 0을 넣어주기로 했다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <stack>
using namespace std;

//블록 사이에 빗물이 고인다.
//빗물의 총량은?

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int h, w, rain = 0;
    int block[501];
    cin >> h >> w;
    for(int i=0; i<w; i++) cin >> block[i];
    for(int i=1; i<w-1; i++){
        int left = 0, right = 0;
        for(int j=0; j<i; j++)     left = max(left, block[j]);
        for(int j=i+1; j<w; j++) right = max(right, block[j]);
        rain += max(0, min(left, right) - block[i]);
    }
    cout << rain << '\n';
    return 0;
}

 

 

 

728x90