(C++) - 백준(BOJ) 14719번 : 빗물 답

www.acmicpc.net/problem/14719

14719번: 빗물

구현 문제였습니다.

 

풀이방법

 1. 왼쪽에서 오른쪽으로 보면서 현재 높이가 이전 높이보다 낮다면 여태까지 가장 큰 높이의 블록높이 - 현재 블록의 높이 즉, 가로에서 i번째 위치에서 고이는 빗물의 높이 값을 d[i][0]에 저장합니다. 만약 높다면 가장 높은 높이의 값을 갱신해줍니다. 

 

 2. 오른쪽에서 왼쪽으로 보면서 같은 방식을 적용합니다.

 

 3. 다시 처음부터 끝까지 보면서 고인 빗물의 최소값을 다 더한뒤 출력해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
//i번째 건물 오른쪽으로
//i번째 건물 왼쪽으로
int h, w, big, ans, world[501], d[501][2];
int main(){
    cin >> h >> w;
    for(int i = 1; i <= w; i++) cin >> world[i];
    big = world[1];
    for(int i = 2; i <= w; i++){
        if(big > world[i]) d[i][0] = big - world[i];
        else big = world[i];
    }
    big = world[w];
    for(int i = w - 1; i >= 1; i--){
        if(big > world[i]) d[i][1] = big - world[i];
        else big = world[i];
    }
    for(int i = 1; i <= w; i++) ans += min(d[i][0],d[i][1]);
    cout << ans;
}