[백준]14719. 빗물

[문제]

 

www.acmicpc.net/problem/14719

14719번: 빗물

 

[풀이]

 

하반기 어느 기업 코테에서 굉장히 이 문제와 유사한 문제가 나왔었다.

 

현재 위치를 기준으로 왼쪽과 오른쪽으로 나누고 

그 중에서 가장 큰 값을  left, right 변수에 저장한다.

 

left와 right 중에서 작은 값을 고르고 여기서 현재 블록의 높이를 빼주면 

해당 블록의 고이는 빗물의 양이 된다.

 

위와 같은 방식으로 두번째 블록부터 마지막 블록 전까지 반복해주면 된다.

 

 

[코드]

 

시간 : 0ms

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int W,H;
int block[MAX]={0,};


int main(void)
{
    int total=0;
    
    cin >> H >> W;
    for(int i=0;i<W;i++)    cin >> block[i];
    
    for(int i=1;i<W-1;i++){
        
        int right=0;
        int left=0;
        
        for(int j=0;j<i;j++)    left = max(left, block[j]);
        for(int j=W-1; j>i;j--) right =max(right, block[j]);
        
        total += max( 0 , min(left,right)-block[i]);
    }
   
    cout << total;
    return 0;
}