BOJ_14719

[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 14316 KB, 시간: 104 ms

분류

구현, 시뮬레이션

제출 일자

2025년 2월 28일 18:39:00

문제 설명

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

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

입력

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

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

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

출력

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

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

문제 풀이

각 위치에서 좌우 최대높이를 저장한 뒤, 그 중 작은 값을 기준으로 물이 고이게 된다. 그리고 고이는 양은 그 위치에서의 높이를 빼주면 된다. 이때 그 위치에서의 높이가 더 크면 고이는 물의 양이 음수로 계산되므로 이를 음수가 아닌 0으로 처리하면 고이지 않는다고 계산이 된다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int H, W, height[], maxL, maxR, maxBoard[][], res;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_14719_빗물/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        maxBoard = new int[W][2];
        maxL = height[0];
        maxR = height[W - 1];

        for (int i = 0; i < W; i++) {
            maxL = (int) Math.max(maxL, height[i]);
            maxBoard[i][0] = maxL;
        }

        for (int i = W-1; i >= 0; i--) {
            maxR = (int) Math.max(maxR, height[i]);
            maxBoard[i][1] = maxR;
        }

        int minH; // 각 인덱스에서 좌우 최대높이 중 작은값 (물이 찰 높이)
        for (int i = 0; i < W; i++) {
            minH = Math.min(maxBoard[i][0], maxBoard[i][1]);
            int water = minH - height[i];
            res += (water > 0 ? water : 0);
        }
        System.out.println(res);
        bw.flush();
        bw.close();
        br.close();
    }
}