[알고리즘] 백준 14719 빗물 자바

www.acmicpc.net/problem/14719

14719번: 빗물

 

 

벽 안에 물을 얼마나 채울 수 있냐는 문제입니다.

 

예제2를 예시로 보면 풀이가 이해하기 쉽습니다.

 

4 8

3 1 2 3 4 1 1 2

1. 양쪽 가장 자리는 물을 채울 수 없습니다.

2. 3번째 인덱스(2) 를  예시로 들면 왼쪽으로는 가장 높은 벽은 3이고 오른쪽에서 가장 높은 벽은 4입니다. 이 중에서 더 작은 벽 높이만큼 물이 채워 집니다. 이게 문제해결의 핵심입니다.

 

풀이는 다음과 같습니다. 

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int[] arr = new int[W];
        int answer = 0;
        for (int i = 0; i < W; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i < W - 1; i++) {
            int current = arr[i]; //현재 벽 높이
            int leftMax = current; //왼쪽 벽 최대높이
            int rightMax = current; //오른쪽 벽 최대높이
            for (int k = i - 1; k >= 0; k--) { //왼쪽 최대벽 높이 탐색
                if (arr[k] > current) {
                    leftMax = Math.max(leftMax, arr[k]);
                }
            }
            for (int k = i + 1; k < W; k++) { //오른쪽 최대벽 높이 탐색
                if (arr[k] > current) {
                    rightMax = Math.max(rightMax, arr[k]);
                }
            }
            if (Math.min(leftMax, rightMax) > current) { // 현재 벽보다 높은 벽이 양쪽에 있는 경우
                answer += (Math.min(leftMax, rightMax) - arr[i]);
            }
        }
        System.out.println(answer);
    }
}