백준 14719번 빗물 [C++]

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

 

 

 

#문제 간단 정리

스택 또는 투포인터 등등 여러 방법으로 풀 수 있는 문제다

 

#문제 해결 방법

좌측 최대 높이들 기록하고 우측 최대 높이를 각각 지점에서 기록한 뒤에

각 지점에서 좌측과 우측 최소 높이에서 현재 높이를 빼주면 

들어갈 수 있는 빗물의 양을 기록할 수 있다.

 

근데 이 풀이 말고도

스택을 사용해서 더 쉽게 풀 수 있다.

1. 스택 사용: 스택을 사용하여 지금까지 만난 블록의 높이 중 높은 블록들의 인덱스를 저장합니다.
2. 높이 비교: 새로운 블록을 만날 때마다 스택의 top에 있는 블록의 높이와 비교합니다.
   • 새로운 블록의 높이가 스택의 top에 있는 블록보다 낮다면, 새로운 블록의 인덱스를 스택에 push합니다.
   • 새로운 블록의 높이가 스택의 top에 있는 블록의 높이보다 크거나 같다면, 스택에서 pop을 수행하고 그 사이에 빗물이 고일 수 있는지 검사합니다.
3. 빗물 계산: 스택에서 두 블록을 pop하여 그 사이에 물이 고일 수 있는지 확인합니다. 물이 고일 수 있는 조건은 다음과 같습니다:
   • 현재 블록 (오른쪽)과 스택에서 pop한 블록 (왼쪽) 사이에 적어도 하나의 블록이 있어야 하며 (즉, 공간이 있어야 하며)
   • 물이 고일 높이는 두 블록 높이의 최소값에서 그 사이 블록의 최대 높이를 빼준 값입니다.

*GPT 씨의 친절한 설명

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

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

    int H, W;
    cin >> H >> W;

    vector<int> blocks(W);

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

    vector<int> left_max(W), right_max(W);

    left_max[0] = blocks[0];
    for (int i = 1; i < W; i++) {
        left_max[i] = max(left_max[i - 1], blocks[i]);
    }

    right_max[W - 1] = blocks[W - 1];
    for (int i = W - 2; i >= 0; i--) {
        right_max[i] = max(right_max[i + 1], blocks[i]);
    }

    int waterResult = 0;

    for (int i = 0; i < W; i++) {
        waterResult += min(left_max[i], right_max[i]) - blocks[i];
    }

    cout << waterResult << "\n";

    return 0;
}

스택 사용 코드

#include <iostream>
#include <stack>
#include <vector>

int main() {
    int H, W;
    std::cin >> H >> W;
    
    std::vector<int> heights(W);
    for (int i = 0; i < W; ++i) {
        std::cin >> heights[i];
    }

    std::stack<int> st;
    int totalWater = 0;

    // 블록들을 순회하면서 물이 고일 수 있는지 확인
    for (int i = 0; i < W; ++i) {
        // 현재의 높이가 스택에 있는 높이보다 크거나 같을 때까지 검사
        while (!st.empty() && heights[st.top()] < heights[i]) {
            int top = st.top();
            st.pop();
            
            // 스택이 비었다면 왼쪽 벽이 없음
            if (st.empty())
                break;
            
            int distance = i - st.top() - 1;
            int bounded_height = std::min(heights[i], heights[st.top()]) - heights[top];
            totalWater += distance * bounded_height;
        }
        
        // 현재 인덱스를 스택에 추가
        st.push(i);
    }

    std::cout << totalWater << std::endl;
    return 0;
}