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

문제링크 : https://www.acmicpc.net/problem/14719

14719번: 빗물

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int H, W, result = 0;

    cin >> H >> W;
    int WH[500];

    for(int i=0; i<W; i++)
    {
        cin >> WH[i];
    }

    for(int i=1; i<W-1; i++)
    {
        int l=0, r=0;

        for(int j=0; j<i; j++)
        {
            l = max(l, WH[j]);  //좌로 가장 큰 값
        }

        for(int k=W-1; k>i; k--)
        {
            r = max(r, WH[k]);  //우로 가장 큰 값
        }

        if(min(l, r) - WH[i] > 0)  //낮은 값을 기준으로 현재 값을 뺌
        {
            result += (min(l, r) - WH[i]);
        }

    }

    cout << result;

    return 0;
}

현재 위치를 기준으로 왼쪽으로 가장 큰 값과 오른쪽으로 가장 큰 값을 각각 저장한다.

빗물이 고이는건 높이가 같아야 하므로, 이 중에서 낮은 값을 선택한다.

그리고 현재 값을 빼면 현재 칸에서의 빗물값을 구할 수 있다.

이를 반복하여 총 빗물량을 구한다.