[백준 14719] 빗물 (JAVA)

문제

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

풀이

생각이 필요한 구현, 시뮬레이션 문제입니다. 풀이 방법은 여러가지 있겠지만 저는 왼쪽에서 오른쪽으로 오른쪽에서 왼쪽으로 한 번씩 지나가면서 값을 변경시켜주는 방식으로 구현하였습니다.

처음 벽들의 높이를 저장 후 왼쪽에서 오른쪽으로 이동하면서 최대 높이를 저장합니다.

벽 높이 : [3, 1, 2, 3, 4, 1, 1, 2]
최대 높이 : [3, 3, 3, 3, 4, 4, 4, 4]
빗물 높이 : [3, 3, 3, 3, 4, 4, 4, 4]

그 후 다시 오른쪽에서 왼쪽으로 이동하면서 벽의 최대 높이를 저장하는데 만약 빗물 높이가 최대 높이보다 크면 최대 높이로 줄이고 빗물 높이가 더 낮으면 그냥 지나갑니다.

벽 높이 : [3, 1, 2, 3, 4, 1, 1, 2]
최대 높이 : [4, 4, 4, 4, 4, 2, 2, 2]
빗물 높이 : [3, 3, 3, 3, 4, 2, 2, 2]

이후 각각의 위치를 빗물높이 - 벽높이를 한 후 더해줍니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] blocks = new int[W];
        int[] rain = new int[W];
        st = new StringTokenizer(br.readLine());

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

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

        System.out.println(ans);
        br.close();
    }
}