이번에 풀어본 문제는
백준 14719번 빗물 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int H,W;
    static int [] rain,blocks;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 맵 크기
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        blocks = new int[W];
        rain = new int[W];

        st = new StringTokenizer(br.readLine());
        int height = Integer.MIN_VALUE;
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
            height = Math.max(height,blocks[i]);
            rain[i] = height;
        }

        int answer = 0;
        height = Integer.MIN_VALUE;
        for(int i = W-1; i >= 0; i--) {
            height = Math.max(height, blocks[i]);
            rain[i] = Math.min(rain[i], height);
            answer += rain[i] - blocks[i];
        }

        System.out.print(answer);
    }
}

📝 풀이

구현 문제입니다.
왼쪽을 기준으로 탐색했을 때, 자신의 왼쪽에 자신보다 높은 높이의 블록이 존재한다면, 해당 블록의 높이만큼 빗물이 찬다고 생각할 수 있기 때문에, 먼저 좌측을 기준으로 탐색을 진행하면서 블록의 최댓값을 rain에 담아줍니다.
하지만 우측 기준으로 진행하면 높이의 차이가 발생하므로, 다음으로는 우측을 기준으로 탐색을 진행하여 좌측을 기준으로 했을 때의 최대 높이와 우측을 기준으로 했을 때의 최대 높이 중 작은 값을 선정하여, 기둥위에 덩그러니 남게 되는 물의 높이를 제외시켜 줍니다.
마지막으로 물의 높이에서 입력된 블록의 높이를 빼주면, 각 기둥 위에 쌓이게 되는 빗물의 크기를 구할 수 있습니다.

📜 후기

간단해 보였으나 굉장히 어려운 문제였습니다 ㅎㅎㅎㅎ..