[백준_14719번] 빗물

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

14719번: 빗물

 

[문제]

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

 

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

[입력 조건]

• 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
• 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
• 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

[코드]

import java.util.*;

public class BaekJoon_14719 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int h=sc.nextInt();
		int w=sc.nextInt();
		
		int[] rain=new int[w];
		for(int i=0;i<w;i++)
			rain[i]=sc.nextInt();
		
		int result=0;
		// 맨 앞과 뒤에는 빗물이 고일 수 없음
		for(int i=1;i<w-1;i++) {
			// 빗물이 고이기 위해서는 현재 높이보다 오른쪽, 왼쪽에 더 높은 블록이 있어야 함
			int left=rain[i];
			int right=rain[i];
			
			for(int j=i-1;j>=0;j--)
				if(rain[j]>rain[i])
					left=Math.max(left, rain[j]);
			
			for(int j=i+1;j<w;j++)
				if(rain[j]>rain[i])
					right=Math.max(right, rain[j]);
			
			// 빈칸에 고이는 빗물 구하기 -> 현재 칸 위에 고이는 빗물의 양만 구함
			if(Math.min(left, right)>rain[i]) {
				result+=Math.min(left, right)-rain[i];
			}
		}
		System.out.println(result);
	}

}

 

[고찰]

 이번 문제의 해결 방법의 핵심은 빗물이 고이는 모든 면적을 생각하는 것이 아닌 현재 칸에서 빗물이 고일 수 있는 양만을 계산하는 것이었다. 맨 앞칸과 뒷칸에는 빗물이 고일 수 없으므로 제외하고 블록 칸수를 저장한 배열을 탐색하면서 현재 위치를 기준으로 양쪽에 자신보다 높은 블록이 있다면 현재 칸 위에 빗물이 고일 수 있는 조건이 된다.  이런 조건을 모든 칸수에 적용해보면서 고이는 빗물의 양을 모두 더하면 고이는 빗물이 총량이 된다.