[백준] 14719번 : 빗물 (C++)

14719번 : 빗물

---

문제)

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

 

 

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

 

 

 

입력 :

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

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

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

 

 

 

출력 :

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

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

 

 

 

 

 

 

풀이)

 

// 14719. 빗물
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<int> vec(m);
    vector<int> prefix_left(m);
    vector<int> prefix_right(m);
    
    // 가장 높은 블록을 저장하기 위한 변수
    pair<int, int> high_left;
    pair<int, int> high_right;
 
    // 배열 입력 받기
    int temp = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> vec[i];
    }
 
    // 왼쪽부터 오른쪽으로 가면서 가장 최댓값과
    // 해당 위치를 저장한다.
    for (int i = 0; i < m; i++)
    {
        if (vec[i] > temp)
        {
            high_left = make_pair(i, vec[i]);
            temp = vec[i];
        }
        prefix_left[i] = temp;
    }
 
    // 오른쪽부터 왼쪽으로 가면서 가장 최댓값과 
    // 해당 위치를 저장한다.
    temp = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        if (vec[i] > temp)
        {
            high_right = make_pair(i, vec[i]);
            temp = vec[i];
        }
        prefix_right[i] = temp;
    }
 
    //
    int answer = 0;
    for (int i = 0; i < m; i++)
    {
        // 왼쪽에 고여있는 빗물
        if (i < high_left.first)
        {
            answer += (prefix_left[i] - vec[i]);
        }
        // 가장 큰 블록 사이에 고여있는 빗물
        else if (high_left.first <= i && i <= high_right.first)
        {
            answer += (high_left.second - vec[i]);
        }
        // 오른쪽에 고여있는 빗물
        else if (high_right.first < i)
        {
            answer += (prefix_right[i] - vec[i]);
        }
    }
 
    cout << answer;
 
    return 0;
}
 

---

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

14719번: 빗물