백준 14719 빗물 (C++)

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

#include <iostream>
#include <vector>

using namespace std;

vector<int> blk;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int h, w;
    int ans = 0;
    cin >> h >> w;

    blk.resize(w);

    for (int i = 0; i < w; i++) {
        cin >> blk[i];
    }



    for (int i = 1; i <= h; i++) {
        //고이는 물의 시작 지점
        int s = -1;
        bool isStart = false;
        //blk[j]<i: 빈 공간
        //blk[j]>=i: 블럭 공간
        for (int j = 0; j < w; j++) {

            if(isStart && blk[j] >= i) {
                ans += j - s - 1;
                isStart = false;
            }
            if (!isStart && blk[j] >= i) {
                if (j != w - 1 && blk[j + 1] < i) {
                    s = j;
                    isStart = true;
                }
            }

        }
    }

    cout << ans;

    return 0;
}

1. 문제

h*w 크기의 2차원 세계가 있다. 이 세계에서 비가 충분히 오면 블럭 사이에 비가 고인다. 1*1 크기에 1의 빗물이 채워진다고 할 때, 빗물의 총량을 출력하라. 단, 빗물이 고이지 않을 경우 0을 출력하라.

2. 풀이

4 8
3 1 2 3 4 1 1 2

이런 입력이 주어졌다고 하면 오른쪽 그림대로 빗물이 차 5가 출력될 것이다. 이를 높이 단위로 잘라서 보면 다음과 같다.

즉, 어떤 빈 공간이 두 블럭 사이에 둘러싸여 있을 경우 빗물이 찰 수 있다. 이를 아이디어 삼아 문제를 풀어보자.

 for (int i = 1; i <= h; i++) {
        //고이는 물의 시작 지점
        int s = -1;
        bool isStart = false;
        //blk[j]<i: 빈 공간
        //blk[j]>=i: 블럭 공간
        for (int j = 0; j < w; j++) {

            if(isStart && blk[j] >= i) {
                ans += j - s - 1;
                isStart = false;
            }
            if (!isStart && blk[j] >= i) {
                if (j != w - 1 && blk[j + 1] < i) {
                    s = j;
                    isStart = true;
                }
            }

        }
    }

 각 빗물이 들어갈 공간은 시작과 끝이 있다. 이 조합이 완성된다면 이 위치에는 빗물이 찰 수 있다. 하나씩 살펴보자

            if (!isStart && blk[j] >= i) {
                if (j != w - 1 && blk[j + 1] < i) {
                    s = j;
                    isStart = true;
                }
            }

시작점이 정해지지 않은 상태에서 블럭이 있고, 그 다음이 빈 공간이면 이는 시작지점이 될 수 있다.

    	if(isStart && blk[j] >= i) {
                ans += j - s - 1;
                isStart = false;
            }

시작점이 정해진 상태에서 빈 공간이 아닌 블럭을 만나면 이를 끝 지점으로 정할 수 있다. 이 사이의 빗물의 양은 양 끝점이 포함되지 않으므로 (끝 지점)-(시작 지점)-1이다. 

 

 어떤 공간의 끝 지점인 동시에 다음 지점의 시작점인 경우가 존재할 수 있으므로 끝 지점 여부를 먼저 확인한다.

연산이 끝나고 총 빗물의 양을 출력하면 정답을 구할 수 있다.