[백준][Java] 14719번 : 빗물

[문제 링크]

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

---

문제 설명

테두리 있는 글상자

 

 

 

 

 

 

문제 풀이

• 구현 문제
• for문을 돌면서 현재 블록 기준으로 오른쪽에서 최대 높이의 블록, 왼쪽에서 최대 높이의 블록을 각각 구한다.
  → maxLeft, maxRight
  
• maxLeft와 maxRight 중 더 작은 값 m을 구한다.
• m이 현재 블록의 높이보다 높을 경우 빗물이 고인다.
  → m - (현재 블록의 높이) 가 현재 블록에 쌓이는 빗물의 양이 된다.
  
• 여기서, 가장 왼쪽 블록과 가장 오른쪽 블록에는 물이 고일 수 없다.
  따라서 for문의 범위는 1 부터 w-1
• 예제2를 그림으로 그려보면 아래와 같다.

 

 

 

전체코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

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

        int result = 0;

        for (int i = 1; i < w - 1; i++) {
            int current = array[i]; //현재 벽의 높이
            int maxLeft = 0;    //왼쪽 최대 블록 높이
            int maxRight = 0;   //오른쪽 최대 블록 높이

            //왼쪽에서 최대 높이 찾기
            for (int j = 0; j < i; j++) {
                maxLeft = Math.max(maxLeft, array[j]);
            }

            //오른쪽에서 최대 높이 찾기
            for (int j = i + 1; j < w; j++) {
                maxRight = Math.max(maxRight, array[j]);
            }

            //왼쪽과 오른쪽의 최대 높이를 비교해서 더 작은 높이 찾기
            int m = Math.min(maxLeft, maxRight);
            if (m > current) {
                result += m - current;
            }
        }
        System.out.println(result);
    }
}

 

 

처음에는 쉬운 문제일 줄 알고 가볍게 접근했는데, 알맞은 풀이 방식을 떠올리는 데 어려움이 있었다. 다른 사람들의 풀이를 참고해서 풀었다.

내가 생각했던 풀이 방식은 하나의 빗물 웅덩이(?)씩 빗물의 양을 구하는 것이다.

예제 2를 보면, 2 개의 웅덩이가 있다.

여기에서 하나의 웅덩이를 감싸는 양 옆의 블록 높이를 구하고, 둘 중 더 낮은 높이에서 웅덩이 내부의 각 블록 높이를 뺀다.

이렇게 해서 빗물을 구하려고 했지만 실패했다.