백준 14719 빗물 / C++

문제 : 14719

풀이 point

빗물을 담으려면 왼쪽과 오른쪽 벽의 차이가 있어야 한다.
i 인덱스 위치의 높이를 기준으로 왼쪽 중(0 <= x < i) 어떤 위치의 값이 가장 큰지 체크한다. 마찬가지로 오른쪽 중(W-1 < x < i) 어떤 위치의 값이 가장 큰지 체크한다.

ex) 예제2

4 8
3 1 2 3 4 1 1 2

인덱스 1 기준으로 왼쪽 중 가장 큰 값은 3 오른쪽 중 가장 큰 값은 4이다. 왼쪽과 오른쪽 중 작은 값을 택한 후(작은 값 까지만 차오를 수 있기 때문) 현재 인덱스의 위치 값 1을 뺀다.
min(3, 4) - 1 => 2칸 차오를 수 있음

참고로 이 값이 음수가 될 수 있기 때문에 0과 비교해서 max값을 취해야한다.

풀이 방법

왼쪽 중 가장 큰 값과 오른쪽 중 가장 큰 값을 뺀 후 현재 위치의 높이를 뺀다.
이 때 l이 r보다 작아서 마이너스 값이 나올 수 있기 때문에 0과 비교해준다.

코드

//백준 14719, 빗물

#include <iostream>

int arr[501];

int main (){

    int H, W;
    std::cin >> H >> W;

    for(int i{0}; i<W; ++i){
        std::cin >> arr[i];
    }

    int cnt{0};
    for(int i{1}; i<W-1; ++i){
        int l{0}, r{0};
        
        for(int j{0}; j<i; ++j) l = std::max(l, arr[j]);
        for(int j{W-1}; j>i; --j) r = std::max(r, arr[j]);
        
        cnt += std::max(0, std::min(l, r)-arr[i]);
    }
    
    std::cout << cnt;

    return 0;
}

사족

컴퓨터적으로 생각하는 것이 아닌 인간적 사고로 생각한 것을 그대로 구현하면 되는 문제지만, 어째서인지 구현이 쉽지 않다고 느껴졌다. 그야말로 하나를 중심으로 양쪽 끝에서 큰값을 구한 후 작은 값 기준으로 빼면 되는 것인데... max값에 홀려 max값 기준 양쪽을 확인한다는 미스를 범했다. 아쉽다.