[백준 14719 with JAVA] 빗물

 

---

• 문제설명
  먼저 첫 번째 줄에 세로, 가로의 길이가 입력되고 두 번째 줄에 가로길이의 개수만큼 숫자들을 입력받는다. 
  두 번째 줄의 숫자는 블록이 높이이다. 위 힌트 사진을 보면 이해하기 수월할 것이다.
  이 블록들 사이에 빗물의 고이는데 고인 빗물의 총합을 구해 출력하면 된다.

• 제출코드     

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int [] block = new int[W];
        int [] rain = new int[W];

        st = new StringTokenizer(br.readLine());

        int height = 0;
        int result = 0;

        for (int i = 0; i < W; i++){
            block[i] = Integer.parseInt(st.nextToken());
            height = Math.max(height, block[i]);
            rain[i] = height;
        }

        height = 0;

        //첫번째줄, 마지막줄 빗물 안고임
        for(int i = W-1; i >= 0 ; i--){
            height = Math.max(height,block[i]);
            rain[i] = Math.min(height, rain[i]);
            result += (rain[i] - block[i]);
        }
        
        System.out.println(result);
    }
}

 

• 코드설명
  먼저 가로길이만큼의 숫자들을 입력받아 block배열에 저장한다. 그리고 rain배열에는 각 칸의 블록의 높이와 이전부터 각 칸까지의 최댓값을 비교해 최대 높이 값들을 저장한다. 
  3 1 2 3 4 1 1 2 이렇게 입력받는다면 block배열에는 차례대로 들어갈 것이고 rain배열에는 3 3 3 3 4 4 4 4 이렇게 들어갈 것이다.
  그리고 이번에는 역으로 for문을 돌려 각 칸에서의 최대 높이 값을 구해줄 것이다. 그리고 이 값과 rain배열의 값과 비교해 더 작은 값을 저장해 줄 것이다.
  height에는 4 4 4 4 4 2 2 2 이렇게 들어갈 것이고 rain배열에는 3 3 3 3 4 2 2 2 이렇게 들어갈 것이다.
  그 후 rain에서 block을 뺀 만큼 빗물이 고일테니 이 값들을 for문을 돌면서 총합을 구하면 된다.