BOJ14179 빗물

https://www.acmicpc.net/problem/14179 (opens new window)

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 빗물의 총량을 구한다.

빗물이 고이기 위한 조건

빗물이 고이기 위해서는 조건이 필요하다.

• 빗물이 고이기 위해선 양쪽에 더 높은 블록이 필요하다.
• 양쪽 블록 중 높이가 낮은 것을 기준으로 빗물이 고이게 된다.

for (int i = 1; i < w - 1; i++) { // (1)

    int right = 0; // (2)
    int left = 0; // (3)

    for (int j = 0; j < i; j++) { // (4)
        left = Math.max(left, graph[j]);
    }

    for (int j = i + 1; j < w; j++) { // (5)
        right = Math.max(right, graph[j]);
    }

    if (graph[i] < left && graph[i] < right) { // (6)
        count += Math.min(left, right) - graph[i];
    }
}

(1) 2차원 세계의 양 끝은 빗물이 고이지 않기 때문에 고려하지 않고 반복문을 진행한다.
(2), (3) 오른쪽과 왼쪽의 높이 최대값을 저장하기 위한 변수이다.
(4), (5) 각 방향의 최대값을 저장한다.
(6) 현재 높이를 기준으로 양쪽 블록의 높이를 확인한다. 만약 현재 높이가 더 높은 경우 빗물이 고이지 않는다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ14179 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int h = scanner.nextInt();
        int w = scanner.nextInt();

        int[] graph = new int[w];

        for (int i = 0; i < w; i++) {
            graph[i] = scanner.nextInt();
        }

        int count = 0;
        for (int i = 1; i < w - 1; i++) {

            int right = 0;
            int left = 0;

            for (int j = 0; j < i; j++) {
                left = Math.max(left, graph[j]);
            }

            for (int j = i + 1; j < w; j++) {
                right = Math.max(right, graph[j]);
            }

            if (graph[i] < left && graph[i] < right) {
                count += Math.min(left, right) - graph[i];
            }
        }

        System.out.println(count);
    }
}

#BOJ #구현 #시뮬레이션