백준 빗물(14719) - 시뮬레이션 기본 java

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1

4 4
3 0 1 4

예제 출력 1

5

예제 입력 2

4 8
3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5
0 0 0 2 0

예제 출력 3

0

힌트

힌트 1:

힌트 2:

힌트 3:

try1

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main{   
    public static void main(String args[]) throws IOException {
        int H, W;
        int left, right, max;
        int result = 0;
        int[] arr;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        arr = new int[W];
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < W; i++){
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        for(int i = 0; i < W; i++){
            left = 0;
            right = 0;
            for(int j = 0; j < i; j++){
                if(arr[j] > left){
                    left = arr[j];
                }
            }

            for(int k = W-1; k > i; k--){
                if(arr[k] > right){
                    right = arr[k];
                }
            }

            max = Math.min(left, right);
            if(max != 0 && max > arr[i]){
                result += max - arr[i];
            }
        }
        System.out.println(result);
    }
}

🔖 Notes

• 문제는 쉽게 이해됐지만 막상 풀어보자니 쉽지는 않았다. 이것 저것 손으로 적어가면서 해보다가 힌트가 떠올랐다.

⚠️ HINT : 현재 블록 기준 왼쪽에서 제일 높은 블록, 오른쪽에서 제일 높은 블록을 찾아서 둘을 비교해서 낮은 블록 - 현재블록 = 고이는 빗물의 양이 나온다.

• 한쪽에 높은 블록이 없거나, 현재 블록이 가장 높다면 result = 0 으로 처리하여 빗물이 고이지 않도록 처리하면 된다.