[BOJ/백준][Gold5] 14719 : 빗물 (C++)

 

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

14719번: 빗물

 

 

[난이도] Gold5
[유형] 구현

[풀이]
0~W-1 열이 있을 때 어떤 인덱스 i 열에 고이는 물의 양을 구하려면
1) 1~i-1 블록의 높이중 최댓값, i+1~W-1 블록의 높이중 최댓값을 구하고
둘중 더 작은 값 k를 구한다.
2) i 블록의 높이 h가 k보다 작다면 물이 고일 수 있고 그 양은 k-h 만큼이다.

이런식으로 1~W-2 블록을 순회하면서 각 열에서 고일 수 있는 물을 더해주면 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int H,W,a[500];
int getMax(int l,int r){
    int ret=0;
    for(int i=l;i<=r;i++){
        ret=max(a[i],ret);
    }
    return ret;
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=0;i<W;i++) scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<W-1;i++){
        int k = min(getMax(0,i-1),getMax(i+1,W-1));
        if(a[i]<k) ans+=k-a[i];
    }
    printf("%d",ans);
} 

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14719.cpp