[BOJ/C++] 빗물(14719번)

1. 개요

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

14719번: 빗물

1-1. 설명

2차원 세계 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 오며, 고이는 빗물의 총량은 얼마인지 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 2차원 세계의 세로 길이 H와 2차원 세계 가로 길이 W가 주어지며, 1 이상 500 이하 정수

 - 두번째 줄에는 블록이 쌓인 높이를 의미하는 0 이상 H 이하 정수가 왼쪽 위치부터 차례대로 W개 주어짐

 - 블록 내부 빈공간이 생길 수 없으며, 2차원 세계 바닥은 항상 막혀있다. 

---

2. 구현

2-1. 풀이

stack에 값을 저장해 풀이를 진행하였다. 여기서 단순히 풀이를 진행하는 것이 아닌, 각 조건들을 신경을 써가며 코드를 구현해야 한다.

 - start의 높이보다 현 높이가 더 크거나 같을 때

 - start의 높이보다 작을 때

 - start의 높이가 더 큰 것이 나오지 않고 끝 원소로 도달했을 때

등 여러 조건들을 생각하며 코드들을 구현하였다. 투포인터로 조금 더 간단하게 구현할 수 있을 것 같다. 다음 번에는 단순 조건 방식이 아닌 다른 알고리즘을 사용해봐야겠다고 생각이 들었다. 

2-2. 코드

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int map[500];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int H, W, result = 0;
    stack<int> stack;
    cin >> H >> W;

    for (int i = 0; i < W; i++) cin >> map[i];

    int start = 0, num, count = 0;
    for (int i = 0; i < W; i++) {
        if (stack.empty() && map[i] == 0) continue; // start 원소가 지정되지 않았고, 0만 나올 때

        if (map[i] != 0 && stack.empty()) { // start 원소가 지정되지 않았고 0이아닌 원소가 등장했을 때
            start = map[i];
            stack.push(start);
            continue;
        }


        if (map[i] >= start) { // start 원소보다 현재 원소가 더 클 때
            num = min(map[i], start);
            while (!stack.empty()) {
                if (stack.size() == 1) { // start만 남았으므로
                    stack.pop();
                    break;
                }
                count += (num - stack.top());
                stack.pop();
            }
            result += count;

            count = 0;
            start = map[i]; // 현재 원소를 start 원소로 지정
            stack.push(start); // 스택에 저장
        }
        else if (i == W - 1) { // 마지막 원소일 때 stack에 들어간 원소 모두 계산
            int end = map[i];

            while (!stack.empty()) {
                num = min(end, start);
                if (stack.size() == 1) { // start만 남았으므로
                    stack.pop();
                    break;
                }

                if (num <= stack.top()) { // 스택의 top 값이 num보다 크거나 같을 때
                    result += count; // 여태 구한 count를 result에 저장
                    count = 0; // top을 기준으로 다시 num을 구해 count 시작
                    end = stack.top();
                }
                else count += (num - stack.top());
                stack.pop();
            }
            result += count;
        }
        else if (map[i] < start) stack.push(map[i]); // start 원소보다 작을 때
    }

    cout << result;

    return 0;
}