[BOJ]14719_빗물_JAVA

--문제--

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

14719번: 빗물

-- 문제 접근 --

문제에 대해서 이해를 하고 풀이법을 생각하는 것이 30분이 소비되었습니다.

위의 사진이 가장 힌트가 가장 잘 나타나 있다고 생각이 듭니다.

여기서 주의할점은 힌트 3을 보시면

위의 사진이여도 빗물은 쌓이지 않는다는 점입니다.

그 이후 생각하여야할건

첫 건물과 마지막 건물에는 빗물이 쌓일 수 없다는 점입니다.

그렇게 하여 생각을 하여 코드를 짜 본다면, 

두 번째부터 끝에서 두번째까지를 고려합니다.

두번째부터 자기의 기준에서

①왼쪽으로 가장 큰 건물 찾기

②오른쪽으로 가장 큰 건물 찾기

③둘 중 작은 값을 구하여 자기보다 더 크다면 빗물이 고일 수 있다고 고려하여 차이만큼 답에 추가를 하는 과정을 진행합니다.

④마지막은 1,2,3 과정을 두 번째부터~끝에서 두 번째까지 과정을 진행하면 답을 구할 수 있습니다.

구현은 쉬운데 생각이 어려웠던 문제였던 것 같습니다.

--코드 구현-- 

package 준비운동;

import java.util.Scanner;

public class BOJ_14719_빗물 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int H=sc.nextInt();
		int W=sc.nextInt();
		int[] map=new int[W];
		//맵 채우기
		for(int i=0;i<W;i++) {
			map[i]=sc.nextInt();
		}
		
		int ans=0;
		int left=0;
		int right=0;
		int curr=0;
		for(int i=1;i<W-1;i++) {
			//현재 기준
			curr=map[i];
			left=0;
			right=0;
			//현재기준에서 왼쪽으로 가장큰 높이의 건물찾기
			for(int j=0;j<i;j++) {
				left=Math.max(left, map[j]);
			}
			//현재기준에서 오른쪽으로 가장 큰 높이의 건물찾기
			for(int k=i+1;k<W;k++) {
				right=Math.max(right, map[k]);
			}
			//둘중 더낮은 건물의 높이에서 자기의 높이의차를 구해서 답 구하기 
			int maxv=Math.min(left, right);
			if(maxv>curr)ans+=maxv-curr;
		}
		System.out.println(ans);
	}

}