빗물

문제 링크

빗물

아이디어

• 스위핑 느낌으로 쭉 지나가면서 해당 열에 채울 수 있는 물의 양을 결정할 수는 없을까?
• 해당 행에 존재하는 블록에 물이 채워지기 위해서는 좌, 우 로 자신보다 높은 높이의 블록이 쌓인 열이 있어야한다.
  • 해당 열에 채워지는 물의 양은 좌, 우 로 자신보다 높은 높이의 블록이 존재해야하고, 그 때 채워지는 물의 양은 min(height[left], height[right]) 이다.

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int H, W;

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

    int answer = 0;
    for (int i = 1; i < W - 1; i++) {
        int l = i - 1, r = i + 1;
        int lm, rm;
        lm = rm = -1;
        while (l >= 0) {
            if (lm == -1 || v[lm] < v[l]) {
                lm = l;
            }
            l--;
            if (l == -1) break;
        }

        while (r < W) {
            if (rm == -1 || v[rm] < v[r]) {
                rm = r;
            }
            r++;
            if (r == W) break;
        }

        if (lm != -1 && rm != W) {
            int minH = min(v[lm], v[rm]);
            answer += max(0, minH - v[i]);
        }
    }
    cout << answer;
    return 0;
}