백준 14719번 : 빗물(Java)

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

14719번: 빗물

---

[풀이]

 

• 처음에는, 오른쪽으로 인덱스를 진행하면서 현재 값보다 높은 곳의 인덱스를 구해 넓이로 계산하려했다.
  • 하지만, 이렇게 하니, 코드가 복잡해지고 인덱스 계산하는 것이 어려워졌다.
• 결국 다른 분들의 코드를 참조했고 좌우 기둥의 가장 높은 인덱스를 계산하는 것에 대해 알게 되었다.
  • 좌우 가장 높은 기둥의 인덱스를 각각 구한 후, 더 낮은 곳의 높이에서 현재 인덱스의 기둥을 뺀 값이 그 곳에 쌓일 빗물의 양이다. 
  • 항상 기준은 for문의 인덱스라는 것을 명심하자. 이 부분이 기점으로 좌우 계산과정을 하는 것이다.

 

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int H, W;

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

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

        for (int i = 0; i < W; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int now = 0;
        int leftValue = 0;
        int rightValue = 0;
        for (int i = 1; i < W - 1; i++) {
            now = arr[i];
            leftValue = arr[i];
            rightValue = arr[i];
            for (int j = 0; j < i; j++) {
                if (arr[j] > now) {
                    leftValue = Math.max(arr[j], leftValue);
                }
            }
            for (int j = i + 1; j < W; j++) {
                if (arr[j] > now) {
                    rightValue = Math.max(arr[j], rightValue);
                }
            }
            answer += Math.min(leftValue, rightValue) - now;

        }
        System.out.println(answer);
    }
}