[백준 14719] 빗물 (C++)

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

 

문제

각 열의 기둥 높이가 주어지고 그 사이에 채워지는 칸의 수를 출력하는 문제

 

접근 방법

이게 맞는 방법인진 모르겠지만 W가 최대 500이어서 왔다갔다 두번하는 식으로 했다.

처음에는 왼쪽에서 오른쪽으로 가면서 지금까지 가장 높았던 기둥(curMax)의 높이와 인덱스를 저장한다.

그러면서 현재 보고 있는 기둥이 curMax 기둥보다 낮을 경우 -> curMax - 현재 기둥 높이 를 tmp에 더한다.

이때 tmp는 임시로 고인 빗물의 양이다.

그리고, 현재 보고 있는 기둥이 curMax 기둥보다 같거나 높을 경우 -> 지금까지의 고인 물이 고이는 것이 확정되므로

tmp 값을 result 에 더해주고 tmp를 0으로 초기화한다.

 

문제는 tmp에 임시로 고인 물이 확정되지 않고 W-1 번까지 보고나서 반영되지 않고 끝나는 경우인데

curMax ~ 블록 끝까지의 고인 물을 다시 돌아가면서 반영해줘야한다.

이때는 반대로 오른쪽부터 왼쪽으로 가면서 고인 빗물의 양을 더해준다.

 

소스코드

#include <iostream>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    
    int result = 0;
    
    int tmp = 0;
    int col[W];
    int curMaxIdx = 0;
    int max = 0;
    for (int i = 0; i < W; i++){
        cin >> col[i];
        if(max <= col[i]){
            curMaxIdx = i;
            max = col[i];
            
            result += tmp;
            tmp = 0;
        } else {
            tmp += max-col[i];
        }
    }
    
    tmp = 0;
    int rMaxIdx = W-1;
    max = 0;
    for(int i = W-1; i >= curMaxIdx; i--){
        if(max <= col[i]){
            rMaxIdx = i;
            max = col[i];
            
            result += tmp;
            tmp = 0;
        } else {
            tmp += max-col[i];
        }
    }
    
    cout << result;
    
    return 0;
}