[백준] 14719번 : 빗물 - 자바(JAVA)

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

14719번: 빗물

 

문제 해석

2차원 세계에 블록이 쌓여있고 비가 오면 블록 사이에 빗물이 고인다.

이때 고이는 빗물의 총량은 얼마일까?

2차원 세계의 바닥을 항상 막혀있다고 가정하여도 좋다.

바닥이 막혀있는 예시

 

문제 풀이 전 설계

 

빗물이 고일 수 없는 상황은 블록의 크기가 작아졌다가 커지는 구간이 없을 때이다.

반대로 빗물이 고일 수 있는 상황은 블록의 크기가 작아졌다가 커지는 구간이 존재할 때입니다.

 

우리가 알아야 할 것은

1. 블록이 작아졌다가 커지는 구간의 시작과 끝점은 어디인가

2. 블록이 작아졌다가 커지는 구간 사이에 블록이 얼마나 존재하는가

 

이 2가지만 알면 됩니다.

 

문제 풀이하면서

Upside와 DownSide를 고려하여

현재 블록보다 이전 블록이 증가하는 구간과 현재 블록보다 이전 블록이 감수하는 구간을 측정하여 시작점과 끝점을 측정하려 했으나 if문이 너무 많아져서 포기하고 다른 분들의 풀이를 찾아봤습니다.

 

블록을 기준으로 왼쪽 오른쪽을 탐색하며 왼쪽에서 가장 높은 블록을 찾고 오른쪽에서 가장 높은 블록을 찾습니다.

이후에 현재 Math.min(오른쪽 블록 가장 높은 블록, 왼쪽 가장 높은 블록)을 하면 그중 낮은 블록의 높이가 나오게 되고 

거기서 현재 블록의 높이를 빼면 빗물이 고이는 량을 측정할 수 있습니다.

이를 1 ~ (너비 -1)까지 반복하면서 더한다면 빗물이 얼마나 고이는지 측정할 수 있습니다.

 

코드

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

public class Main_14719_빗물 {
	private static int H, W;
	private static int[] blockArray;
	private static int left, right, center;
	
	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());
		
		blockArray = new int[W];
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i=0; i<W; i++) {
			blockArray[i] = Integer.parseInt(st.nextToken());
		}
		
		left = center = right = 0;
		
		//5 4 2 3 4 6
		
		//가운데 기준으로 왼쪽 오른쪽 큰 친구를 찾는다.
		for (int i=1; i<W-1; i++) {
			left = right = 0;
			//i기준 왼쪽 중 제일 높은 친구 찾기
			for (int j=0; j<i; j++) {
				left = Math.max(left, blockArray[j]);
			}
			
			//i기준 오른쪽 중 제일 높은 친구 찾기
			for (int j=i+1; j<W; j++) {
				right = Math.max(right, blockArray[j]);
			}
			
			//현재 block이 left와 right보다 작으면 더해주기
			if (blockArray[i] < left && blockArray[i] < right) {
				center += Math.min(left, right) - blockArray[i];
			}
			
		}
		
		System.out.println(center);
	}
	
	
}