[ BOJ ][JAVA][14719] 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	3306	1747	1399	54.415%

문제

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

코드

import java.io.*;
import java.util.*;

public class p14719 {
    static int h, w, ans;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ans = 0;
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        arr = new int[w];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < w; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 각 인덱스마다 모이는 빗물은 계산한다. (첫번째 기둥과 마지막 기둥은 제외)
        for (int i = 1; i < w - 1; i++) {
            int current = arr[i];
            int leftMax = current;
            int rightMax = current;

            // 왼쪽에서 가장 높은 기둥의 높이
            for (int k = i - 1; k >= 0; k--) {
                if (arr[k] > current) {
                    leftMax = Math.max(leftMax, arr[k]);
                }
            }

            // 오른쪽에서 가장 높은 기둥의 높이
            for (int k = i + 1; k < w; k++) {
                if (arr[k] > current) {
                    rightMax = Math.max(rightMax, arr[k]);
                }
            }

            // 현재 벽보다 높은 벽이 양쪽에 있는 경우
            if (Math.min(leftMax, rightMax) > current) {
                ans += Math.min(leftMax, rightMax) - arr[i];
            }
        }
        System.out.println(ans);
    }
}