[백준] 빗물 14719번 (c++) 구현

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

풀이 방법

x좌표를 기준으로 현재 지역은 왼쪽에서 가장 큰 값과 오른쪽에서 가장 큰 값 중 작은 값에서 자신의 블록 높이를 뺀 만큼 물이 차오르게 된다.

그러므로 각각의 왼 쪽 최댓값과 오른쪽 최댓값을 구해 자신의 블록 길이만큼 빼주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    vector<int> block;    
    int H, W;
    cin >> H >> W;
    int answer = 0;

    for (int i = 0; i < W;i++) {
        int a;
        cin >> a;
        block.push_back(a);
    }        
    for (int i =1;i < W-1;i++) { // 처음과 끝은 생략한다.
        int left = 0, right = 0;
        for (int k = i; k >= 0; k--) {
            left = max(left, block[k]);
        }
        for (int k = i; k < W;k++) {
            right = max(right, block[k]);
        }
        answer += max(0, min(left, right) - block[i]);
    }
    cout << answer;
    return 0;
}