[백준/C++]#14719- 빗물

코드1

// BOJ #14719

#include <bits/stdc++.h>

using namespace std;

// 2차원 블록 세상
bool block[501][501];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int H, W, inp;
    cin >> H >> W;
    for (int i=1; i<=W; i++) {
        // 블록의 크기
        cin >> inp;
        // 해당 열의 맨 아랫줄부터 블록의 크기만큼 채움 
        for (int j=H; j>H-inp; j--) {
            block[j][i] = 1;
        }
    }
    // 한 줄에 존재하는 블록 저장용 큐
    queue<int> q;
    // 빗물의 양
    int sum=0;
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++) {
            // 블록 존재하면 저장
            if (block[i][j]) q.push(j);
            // 존재하는 블록이 2개가 되면, 계산 및 첫 블록 제거
            if (q.size() == 2) {
                sum+=(j - q.front()-1);
                q.pop();
            }
        }
        // 한 줄에서 사용한 큐 초기화
        while (!q.empty()) q.pop();
    }
    cout << sum;
    return 0;
}

풀이

한 줄에 대해, (두 블록 사이의 길이-1)이 빗물이 차는 공간

1. 입력값으로 2차원 세상을 2차원 배열에 입력받음
2. 2차원 배열을 돌며, 한 줄에 블록이 존재하면 큐에 저장
3. 그리고 큐의 크기가 2가 되면, 총 빗물 양에 추가하며 먼저 넣은 블록을 제거함