[백준]14719: 빗물 - JAVA

[백준]14719: 빗물

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

14719번: 빗물

풀이

문제는 구현 문제로 쉽게 이해할 수 있는 문제였다.

 

빗물이 고이기 위한 조건들을 살펴보쟝. 아래와 같다. 

• 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다.
• 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다.
• 첫, 마지막 블록에는 빗물이 고일 수 없다.

 

인덱스 별로 모이는 빗물의 정보를 더해준 다음 출력해주면 된다. 현재 인덱스를 기준으로 왼쪽에서 가장 높은 블럭과 오른쪽에서 가장 높은 블럭을 구해준 다음, 현재 블럭이 두 블럭보다 낮은지 확인 후, 둘 중에 더 낮은 기둥을 기준으로 낮은 기둥에서 현재 기둥높이를 빼 주어 빗물이 고일 수 있는 높이를 계산해 주었다.

 

코드

import java.util.*;
 
public class Main {
 
    static int h, w;
    static int[] height;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        h = scan.nextInt();
        w = scan.nextInt();
 
        height = new int[w];
        for(int i = 0; i < w; i++) {
            height[i] = scan.nextInt();
        }
 
        int result = 0;
        for(int i = 1; i < w - 1; i++) { //인덱스 별 모이는 빗물. 첫, 마지막 제외
            int left = 0;
            int right = 0;
 
            for(int j = 0; j < i; j++) {
                left = Math.max(height[j], left);
            }
 
            for(int j = i + 1; j < w; j++) {
                right = Math.max(height[j], right);
            }
 
            if(height[i] < left && height[i] < right) result += Math.min(left, right) - height[i];
        }
        System.out.println(result);
    }
}