[백준 - 14719] 빗물

- 문제설명

 

 

- 풀이코드

 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void){
 
    int h,w;
    int answer = 0;
    cin >> h >> w;
 
    vector<int> blocks(w,0);
 
    for(int i=0;i<w;i++){
        cin >> blocks[i];
    }
 
    for(int i=1;i<w-1;i++){
        
        int i_th = blocks[i];
        int left_max,right_max;
        
        left_max = *max_element(blocks.begin(),blocks.begin()+i+1);
        right_max = *max_element(blocks.begin()+i,blocks.end());
 
        answer += min(left_max,right_max) - i_th;
 
    }
 
    cout << answer;
 
    return 0;
}

 

- 시간복잡도

 

공간의 너비를 n개라 했을 때 O(n^2)

 

- 풀이

 

i번째 블럭을 기준으로 좌측 최대 높이블럭과 우측 최대 높이블럭을 찾아서 둘 중 높이가 낮은 블럭과 i번째 블럭의 높이차 만큼 빗물이 쌓인다고 생각하여 푼 문제이다. 주의해야할 점은 좌우측 최대 높이를 구할때 i 번째 블럭을 포함해야 한다는 점이다. 포함하지 않으면 0 0 0 2 3 또는 2 2 2 2 4 5 와 같은 입력에서 음수 값을 답으로 도출해내기 때문이다. 

- Reference

www.acmicpc.net/problem/14719