[백준 / Java] 14719 빗물

문제

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

 

 

문제 개요

2차원 세계에서 블록이 쌓여 있을 때, 비가 온 후 고일 수 있는 빗물의 총량을 구하는 문제입니다. 각 블록의 높이가 주어지며, 블록 사이에 움푹 파인 공간이 있으면 빗물이 고입니다. 고일 수 있는 물의 총량을 계산하여 출력하면 됩니다.

 

 

문제 접근 방법

1. 각 위치에서 고일 수 있는 빗물 계산
   • 특정 위치 i에서 고일 수 있는 빗물의 양은
     "해당 위치에서 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 작은 값"에서 현재 블록의 높이를 뺀 값입니다.
   • 즉, water[i]=min(leftMax[i],rightMax[i])−height[i]
   • 이를 위해, 각 위치에서 왼쪽과 오른쪽의 최대 높이를 미리 구해둡니다.
2. 왼쪽 최대 높이(left 배열) 계산
   • left[i]는 0번 인덱스부터 i까지의 블록 중 가장 높은 높이입니다.
   • 이를 left[i] = max(left[i-1], height[i])로 계산합니다.
3. 오른쪽 최대 높이(right 배열) 계산
   • right[i]는 i부터 끝까지의 블록 중 가장 높은 높이입니다.
   • 이를 right[i] = max(right[i+1], height[i])로 계산합니다.
4. 최종 빗물 계산
   • 각 위치에서 min(left[i], right[i]) - height[i] 값을 더하여 총 빗물의 양을 구합니다.

 

코드

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

public class Main {
    static int H, W;
    static int[] right, left, arr;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(cal());
    }

    public static int cal() {
        int cnt = 0;

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

        return cnt;
    }

    public static void init() 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());

        st = new StringTokenizer(br.readLine());
        arr = new int[W];
        right = new int[W];
        left = new int[W];

        for(int i=0; i<W; i++) arr[i] = Integer.parseInt(st.nextToken());

        right[0] = arr[0];
        for(int i=1; i<W; i++) right[i] = Math.max(right[i-1], arr[i]);

        left[W-1] = arr[W-1];
        for(int i=W-2; i>=0; i--) {
            left[i] = Math.max(left[i+1], arr[i]);
        }
    }
}