백준/14719 빗물

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 빗물 문제는 leftMax, rightMax를 활용했다.

  • leftMax[i] : 왼쪽부터 i번째 까지 가장 큰 높이를 저장한다.

  • rightMax[i] : 오른쪽부터 i번째 까지 가장 큰 높이를 저장한다.

  • 이후 i번째에 담을 수 있는 빗물은 leftMax[i]와 rightMax[i] 값중 작은 값에서 block[i]의 값을 뺀 값이 된다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(stk.nextToken());
        int w = Integer.parseInt(stk.nextToken());
        int[] block = new int[w];
        int[] leftMax = new int[w];     //왼쪽에서부터 가장 큰 block의 크기
        int[] rightMax = new int[w];    //오른쪽에서부터 가장 큰 block의 크기
        stk = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < w; i++) {
            block[i] = Integer.parseInt(stk.nextToken());
            max = Math.max(max, block[i]);
            leftMax[i] = max;
        }
        max = 0;
        for (int i = w - 1; i >= 0; i--) {
            max = Math.max(max, block[i]);
            rightMax[i] = max;
        }
        int sum = 0;
        for (int i = 0; i < w; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);        //둘중 작은값을 선택
            if (min - block[i] > 0) sum += min - block[i];      //min > block[i]라면 그 차이만큼 빗물을 담을 수 있다.
        }
        System.out.println(sum);
    }
}