구현 및 시뮬레이션

12 May 2021

Reading time ~1 minute

빗물 (백준)

풀이 전략 : 내 자신을 기준으로 왼쪽 오른쪽을 검색한 다음 왼쪽기준 가장 큰놈과 오른쪽 기준 가장 큰놈 중 제일 작은놈을 기준으로 나 자신을 빼면 해당 위치에서 받을 수 있는 물의 양이 나옴
c++의 max, min 활용

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int main(){
    int N, M;
    int ans = 0;

    cin >> N >> M;
    vector<int> v(M);

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

    for(int i=1; i<M-1; i++){
        int left = 0;
        int right = 0;
        for(int j=0; j<i; j++){
            left = max(left, v[j]);
        }
        for(int j=M-1; j>i; j--){
            right = max(right, v[j]);
        }
        ans += max(0, min(left, right) - v[i])
    }
    printf("%d", ans);
}

Algorithm