[백준 JAVA] 14719번: 빗물

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

 

이중포문으로 왼쪽 기둥과 오른쪽 기둥을 구한뒤 그 사이에 있는 빗물을 계산하려 했는데 실패했다.

 

이 문제를 가장 쉽게 풀 수 있는 방법은 해당 위치에서 좌 우의 최대 높이를 구한 뒤 현재 블록 위에 고인 빗물을 계산하는 방식이다.

 

막대 i 위에 고이는 빗물 = min(좌측 최고 높이, 우측 최고 높이) - 현재 높이 (음수면 0)

그래서:

1. leftMax[i]: i 기준 왼쪽까지의 최고 높이
2. rightMax[i]: i 기준 오른쪽까지의 최고 높이
3. 모든 i에 대해 위 식을 더하면 끝.

이런식풀면 O(W) 만에 풀이가능하다.

 

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

public class Main {
    public static int H, W, ans = 0;
    public static int[] arr, left, right;
    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());

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

        left = new int[W];
        right = new int[W];

        // 왼쪽 최대
        left[0] = arr[0];
        for(int i = 1; i < W; i++){
            left[i] = Math.max(left[i-1], arr[i]);
        }

        // 오른쪽 최대
        right[W - 1] = arr[W - 1];
        for(int i = W - 2; i >= 0; i--){
            right[i] = Math.max(right[i + 1], arr[i]);
        }

        for(int i = 0; i < W; i++){
            int water = Math.min(left[i], right[i]) - arr[i];
            if(water > 0) ans += water;
        }

        System.out.println(ans);

    }
}