[백준] 15719번: 빗물

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

14719번: 빗물

진짜 울고 싶다 으헝헝 8ㅅ8

아무리 풀어도 제대로 못 푼다...심지어 이거 골드5인데.. 계속 꼬인다..

 

문제를 쉽게 풀어내도록 접근했어야 했는데

괜히 이중 for문을 쓰면서 어렵게 풀려고 했다.

최대한 간결하고 쉽게 풀 생각을 우선 해야할 것 같다.

 

빗물이 쌓이는 구간을 이중 for문으로 구하려 했는데, 이렇게 되면 예외가 많이 생기고 복잡해진다.

대신 한 점씩 각각 for문을 하나씩 쓰면서 왼쪽 벽, 오른쪽 벽을 구해서 각 칸마다 고이는 빗물의 총량을 구하는 게 빠르다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int h, w, answer = 0;
    cin >> h >> w;
    vector<int> heights(w);
    for(int i = 0;i < w;i++) {
        cin >> heights[i];
    }
    
    for(int i = 1;i < w;i++) {
        int left, right;
        left = right = 0;
        for(int j = 0;j < i;j++) left = max(left, heights[j]);
        for(int j = i + 1;j < w;j++) right = max(right, heights[j]);
        
        int result = min(left, right) - heights[i];
        if(result >= 0) answer += result;
    }

    cout << answer << '\n';

}