[백준 14719] - 빗물 c++

문제

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

14719번: 빗물

접근방법

막대기 사이 빗물을 채우기 위해서 배열을 2개 만들었다.

최고점을 저장하는 배열 arr와 블록이 쌓인 모양 그대로 2차원배열 block이다.

 

최소 w>2 이상일 때 빗물이 채워질 수 있다.

따라서 i = 2 부터 시작해서 block을 횡으로 탐색할건데,

이때 block의 높이인 arr[i]를 받아와서 heigth로 저장한다.

height는 세로위치, j는 가로 위치를 의미한다.

 

j--를 통해 뒤로 이동하면서 블록이 있는 지 확인한다.

블록과 부딪히는 순간 그 사이를 width에 저장하고,

다시 height를 한 칸 아래로 옮기고 같은 작업을 진행한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int h, w;
    cin >> h >> w;
    vector<vector<int> > block(h, vector<int>(w, 0));
    vector<int> arr(w);
    for (int i=0;i<w;i++) {
        int temp;
        cin >> temp;
        arr[i] = temp;
        for (int j=0;j<temp;j++) {
            block[j][i] = 1;
        }
    }
    int sum = 0;
    for (int i=2;i<w;i++) {
        int height = arr[i];
        int width = 0;
        while(height--) {
            int j = i;
            while(block[height][--j] == 0 && j >= 0);
            if (j < 0) continue;
            width += (i-j) - 1;
        }
        sum += width;
    }

    cout << sum << endl;

    return 0;
}

개선할 점

while(block[height][--j] == 0 && j >= 0);

이 부분이 조금 맘에 걸렸는데, 그냥 통과됐다.

--j가 먼저 적용되고 j>=0를 하게 된다면, 인덱스 -1을 참조하게 되어 out of bound가 발생하지 않을까 싶었다.