백준 14719 빗물

문제링크:https://www.acmicpc.net/problem/14719
난이도: 골드 5
알고리즘: 구현,시뮬레이션
풀이 idea: 빗물이 고일때, 양끝 블록은 빗물이 고일 수 없다. 왜냐? 양끝옆에는 아무 블록도 존재하지 않기 때문!
빗물이 고일수 있는 조건은 나보다 높이가 큰 블록이 왼쪽과 오른쪽에 존재할 경우 빗물이 고일 수 있다.
for문을 통해 양끝 블록을 제외한 모든 블록을 기준으로 잡고 기준 블록으로부터 가장 왼쪽까지 높이가 제일 높은 값을 저장한다. 오른쪽도 동일하게 진행한다.
왼쪽 오른쪽의 높이가 큰 값을 각각 구한후, 두개의 값중 작은값에서 현재의 위치 높이를 뺀 값을 저장하면 된다.
for문을 빠져나와 저장한 값을 출력하면 정답이 된다.

풀이코드:

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

using namespace std;

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    
    int h,w;
    cin>>h>>w;
    vector<int>v(w);
    for(int i=0;i<w;i++){
        cin>>v[i];
    }
    int res=0;
    
    for(int i=1;i<w-1;i++){
        
        int lt=i-1;
        int rt=i+1;
        int lmax=v[i];
        int rmax=v[i];
        while(lt>=0){
                lmax=max(v[lt--],lmax);
        }
        while(rt<w){
           
                rmax=max(v[rt++],rmax);
            
        }
        res+=min(rmax,lmax)-v[i];
        
        
        
        
        
    }
    
    
    
    cout<<res<<"\n";
    
    
    return 0;
}