[백준] 빗물 14719 - JAVA

문제

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

14719번: 빗물

풀이

빗물이 고이려면 다음과 같아야 한다.

• 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다.
• 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다.
• 첫, 마지막 블록에는 빗물이 고일 수 없다.

각 인덱스를 기준으로 오른쪽과 왼쪽의 높은 블록을 구하고 차이값을 구한다.

코드

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 height [] = new int [w];
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<w;i++) {
			height[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = 0;
		
		for(int i=1;i<w-1;i++) {
			int left = 0;
			int right = 0;
			
			for(int j=0;j<i;j++) {
				left = Math.max(left, height[j]);
			}
			
			for(int j=i+1;j<w;j++) {
				right = Math.max(right, height[j]);
			}
			
			int min = Math.min(left, right);
			
			if(min - height[i] > 0)
				result += min - height[i];
		}
	
		System.out.print(result);
	}
	

}