백준 14719 자바 - 빗물 (BOJ 14719 JAVA)

문제 : boj14719

 

 

  '문제'에 나온 이미지를 다시 그려봤다.

이 때 물이 차는 높이를 어떻게 알 수 있을까? 우선 3D로 생각해서 좌측에서 블록들을 본다고 생각해보자.

이 때 물은 좌측에서 시선에 닿는 만큼 차오를 수 있다. 즉 좌측에서 봤을 때 눈에 보이는 부분들에 들어찰 것이다. 좌측에서만 보면 아래와 같이 생각할 수 있다. 이 때 우측은 당연히 저렇게 들어차면 안된다. 따라서 우측에서도 확인해야 한다.

 

이번엔 우측에서 한번 봐본다고 생각해보자.

 

그럼 이렇게 생각될 수 있다. 

 

그럼 이제 좌측에서 본 것과, 우측에서 본 것을 합쳐서 각 블록마다 좌측에서 봤을때와 우측에서 봤을 때 보였던 높이 중 작은 쪽을 선택하면 아래와 같이 된다.

 

 

좀 더 구체적으로 정의하자면 다음과 같다.

좌측부터 w방향으로 i번째 블록의 높이를 height[i]라 하고, 현재 판단하기에 해당 블록의 위치에 들어찰 물의 높이를 arr[i]라 하고 tmp 라는 변수를 하나 두겠다.

 

그럼 이제 i를 증가시키면서 봐보면 좌측방향에서 보고 있는게 된다. 이 때 tmp = max(tmp, height[i])가 되고, arr[i] = min(arr[i], tmp)가 될 것이다. 이렇게 진행한 후,

이번엔 i를 맨 우측부터 감소시키면서 똑같이 수행하게 된다면 위에서 설명한 방식으로 차오르는 높이를 구할 수 있다. 

 

 

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int w = Integer.parseInt(br.readLine().split(" ")[1]);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[][] arr = new int[2][w];
        Arrays.fill(arr[1], 500);
        for (int i = 0; i < w; i++) arr[0][i]=Integer.parseInt(st.nextToken());
        int lmax = 0, rmax = 0;
        for (int l = 0, r = w-1; l < w; l++, r--) {
            arr[1][l] = Math.min(arr[1][l], (lmax = Math.max(lmax, arr[0][l])));
            arr[1][r] = Math.min(arr[1][r], (rmax = Math.max(rmax, arr[0][r])));
        }
        int sum = 0;
        for (int i = 0; i < w; i++) sum += arr[1][i]-arr[0][i];
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}