[백준] 14719. 빗물

문제 링크

[백준] 14719. 빗물

풀이 과정

첫 번째 블럭과 마지막 블럭은 빗물이 고일 수 없기 때문에 제외시키고, 나머지 구간에 해당하는 인덱스 1부터 W - 1까지의 범위에 해당하는 블럭들을 대상으로, 각각 고이는 빗물의 양을 계산합니다.

1번 블럭을 보면, 블럭 기준 좌측의 가장 높은 블럭의 높이는 3, 우측의 가장 높은 블럭의 높이는 4가 됩니다. 결국, 그 값중 작은 값인 left의 높이만큼 빗물이 고인다는 것을 확인할 수 있습니다.

3번 블럭을 보면, 블럭 기준 좌측의 가장 높은 블럭은 존재하지 않고, 우측의 가장 높은 블럭의 높이는 4가 됩니다. 빗물의 양은 블럭을 감싸는 양쪽 블럭 중 더 낮은 높이를 갖는 블럭에 의해 결정되기 때문에, 자기자신을 가리키는 left가 결정을 짓게 되고, 이번에는 빗물이 고이지 않게 됩니다.

for (int i = 1; i < W; i++) {
    int left = heights[i], right = heights[i];

    for (int j = 0; j < i; j++) left = Math.max(left, heights[j]);
    for (int j = i + 1; j < W; j++) right = Math.max(right, heights[j]);

    int min = Math.min(left, right);
    answer += min - heights[i];
}

코드로 옮기면 위와 같이 작성됩니다. 모든 블럭에 대하여 answer += min - heights[i]; 를 수행하지만, 양 블럭 중 더 낮은 높이를 가리키는 min 값이 자기 자기 자신의 높이와 같다면, 결국 0을 누적시키게 됩니다.

코드

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int[] heights = new int[W];
        int answer = 0;

        for (int i = 0; i < W; i++) heights[i] = sc.nextInt();

        for (int i = 1; i < W; i++) {
            int left = heights[i], right = heights[i];

            for (int j = 0; j < i; j++) left = Math.max(left, heights[j]);
            for (int j = i + 1; j < W; j++) right = Math.max(right, heights[j]);

            int min = Math.min(left, right);
            answer += min - heights[i];
        }

        System.out.println(answer);
    }
}