[Java] 백준 14719번 : 빗물

1. 문제

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

14719번: 빗물

 

 

2. 풀이 과정

처음에 어떤 알고리즘을 쓰지 등 복잡하게 생각하지 않고, 문제만 생각하는 습관을 길러야 될 것 같다.

 

한 column에서 최대 채울 수 있는 물의 양을 구하는 방법은 아래와 같다.

1. 해당 column 왼쪽과 오른쪽 각각에서 블럭의 최대 높이를 찾기

2. 둘 중 작은 값만큼 채울 수 있음

 

구현방법

1. 해당 column마다 자신의 왼쪽에 있는 블럭 중 최대 높이를 1차원 배열에 저장
2. 해당 column마다 자신의 오른쪽에 있는 블럭 중 최대 높이를 구함과 동시에 왼쪽, 오른쪽 중 작은 값만큼 채울 수 있는 빗물 수를 계산한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputs[] = br.readLine().split(" ");
        int M = Integer.parseInt(inputs[1]);
        inputs = br.readLine().split(" ");
        int arr[] = new int[M], left[] = new int[M];

        int l = 0, r = 0, result = 0;
        for(int i=0; i<M; i++){
            arr[i] = Integer.parseInt(inputs[i]);
            left[i] = Math.max(l, arr[i]);
            l = left[i];
        }

        for(int i=M-1; i>=0; i--){
            r = Math.max(r, arr[i]);
            result += Math.min(left[i], r) - arr[i];
        }
        System.out.println(result);
    }
}

 

 

결과