[Java] 백준 14719 - 빗물

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

정답 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] size = br.readLine().split(" ");
        int answer = 0;
        int H = Integer.parseInt(size[0]);
        int W = Integer.parseInt(size[1]);

        String[] heights = br.readLine().split(" ");
        int[] blocks = new int[W];
        for (int i = 0; i < heights.length; i++) {
            blocks[i] = Integer.parseInt(heights[i]);
        }

        for (int i = 1; i < W - 1; i++) {
            int lm = 0;
            int rm = 0;

            int current = blocks[i];

            //현재 블록의 왼쪽에 있는 모든 블록 중 가장 높은 블록
            for (int j = i - 1; j >= 0; j--) {
                lm = Math.max(lm, blocks[j]);
            }
            //현재 블록의 오른쪽에 있는 모든 블록 중 가장 높은 블록
            for (int j = i + 1; j < W; j++) {
                rm = Math.max(rm, blocks[j]);
            }

            //lm, rm 둘다 현재 블록보다 크면, answer+= 둘 중 낮은 블록 - 현재 블록
            if (lm > current && rm > current) {
                answer += Math.min(lm, rm) - current;
            }
        }

        System.out.println(answer);
    }
}

시나리오

1. 처음과 마지막블록에 빗물이 고일 수는 없으므로 그 사이 블록들만 순회
2. 현재 블록의 모든 왼쪽 블록 중 가장 큰 값, 현재 블록의 모든 오른쪽 블록 중 가장 큰 값을 각각 lm, rm으로 저장
3. lm,rm이 현재 블록보다 크면 둘 중 더 작은값에 현재 블록이 높이를 뺀 값을 answer에 더함

현재 블록보다 높은 블록이 왼쪽, 오른쪽에 존재해야 빗물이 고이며, 고이는 빗물의 양은 (더 높은 두 블록 중 낮은 블록-현재 블록)이라는 규칙을 이용한 시나리오이다.
나는 이 규칙을 찾지 못했고, 대신 이전 블록보다 더 큰 블록이 나오면 그 사이의 있는 빗물양을 모두 더하는 방법으로 문제를 풀었다. 테스트 케이스는 맞았는데 엣지 케이스를 찾지 못해 이 시나리오로 정답처리를 받진 못했다.
지금 생각해보면 중간에 기존에 갱신된 큰 블록 변수보다 작은 블록이 나오면 무시되기 때문에 오답을 받은 것 같다.
여튼.. 규칙을 더 잘찾아야 하는디 짱구좀 더 굴려보자