백준 14719번 빗물 - C++ 풀이

---

 

1. 각 열마다 고이는 빗물의 양을 구해 합친다.
2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다.
3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다.

 

1. 각 열마다 고이는 빗물의 양을 구해 합친다.

 각 열마다 고이는 빗물의 양을 구한 뒤 합치는 방식으로 전체 고이는 빗물의 양을 구해준다. 이때 양 끝 열(제일 왼쪽과 오른쪽)에는 절대 빗물이 고일 수 없다.

 

2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다.

 빗물이 고이기 위해서는 그릇의 형태가 되어야 한다. 즉, 양쪽이 i열보다 더 높은 블록으로 막혀있어야 한다. (양 끝 열에는 절대 빗물이 고일 수 없는 이유이다.) 또한 그릇 안에 더 작은 그릇이 들어있더라도 결국에는 가장 큰(바깥) 그릇이 꽉 찰 때까지 빗물이 고인다. 마찬가지로 i열을 둘러싸고 있어 그릇의 벽면이 되어줄 수 있는 블록은 여러 개이더라도, 빗물의 양을 결정하는 것은 그 중 가장 높은 블록이다. 왼쪽 벽면과 오른쪽 벽면이 되어줄 가장 높은 블록들을 각각 찾아주자. 0열 ~ (i-1)열에서 가장 높은 블록이 왼쪽 벽면, (i+1)열 ~ (W-1)열에서 가장 높은 블록이 오른쪽 벽면이다.

 

3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다.

 이제 두 벽면 중 더 낮은 곳의 높이를 limit이라고 하자. i열의 블록 높이를 h[i]라 하면, 빗물은 최대 limit - h[i]만큼 고이게 될 것이다. 그런데 만약 벽면 후보인 블럭이 i열 보다 낮다면 해당 블록은 벽면이 될 수 없다. 따라서 이러한 경우는 예외 처리해주어야 한다. 이러한 경우에는 limit < h[i]이기 때문에 limit - h[i]가 음수가 되므로, max(0, limit - h[i])를 통해 간단하게 예외처리할 수 있다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calcRainwaterInColumn(int c, vector<int>& heights) {
    vector<int>::iterator s = heights.begin();
    vector<int>::iterator e = heights.end();
    
    // 둘러싸고 있는 양쪽 블록 중 각각 가장 높은 블록을 구함
    int left_max = *max_element(s, s + c);
    int right_max = *max_element(s + c + 1, e);
    
    // 그 중 더 낮은 블록 높이까지 빗물이 고임
    int limit = min(left_max, right_max);
    int accumulated_rainwater = max(0, limit - heights[c]);
    
    return accumulated_rainwater;
}

int solution(int H, int W, vector<int>& heights) {
    int answer = 0;
    
    // 양 끝 열에는 고일 수 없음
    for (int i = 1; i < (W - 1); i++) {
        answer += calcRainwaterInColumn(i, heights);
    }
    
    return answer;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int H, W;
    vector<int> heights;
    
    cin >> H >> W;
    heights.resize(W);
    for (int i = 0; i < W; i++) {
        cin >> heights[i];
    }
    
    cout << solution(H, W, heights);

    return 0;
}