창고 다각형

문제

이문제를 처음 봤을때 매우 어렵게 느껴졌다. 이후 여러 그림을 그리면서 문제의 방향성을 찾은것 같다.

(그림으로 그리면 이해 하기 훨씬 쉬운것 같다.)

index의 최저점 최고점을 알고 Max Height를 갱신해가는 방식으로 문제를 접근하였다 위 그림의 첫번째 그림처럼 부분을 빼주면 우리가 원하는 그림을 얻을 수 있다. 부분을 빼는 방법은 가장 끝의 index에서 이전에 갱신한 최대값을 만날때 까지 가는데  이 문제에는 조건이 존재하는데 물이 고이는 부분이 없어야한다(구덩이). 이 조건은 두번째 그림을 보면 이해 할 수 있다. 구덩이가 생기는 조건은 MaxIndex에서 이동하면서 그 값이 변동될때 즉, 큰 값이 등장할 때 그 값을 갱신해주고 더해주면 첫번째 구했던 면적 - 두번째 구했던 면적 을 구해주면 문제에서 원하는 가장 작은 면적을 구할 수 있다.

 

import java.util.*;
import java.util.StringTokenizer;
 
public class Main{
    public static int result=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int number=sc.nextInt();
        int [] arr = new int [1001];//N이 1000이하 
        int minIndex=Integer.MAX_VALUE;
        int maxIndex=Integer.MIN_VALUE;
        for(int i=0;i<number;i++)
        {
            int index=sc.nextInt();
            int height=sc.nextInt();
            arr[index]=height;
            if(index>maxIndex)
            {
                maxIndex=index;
            }
            if(index<minIndex)
            {
                minIndex=index;
            }
        }
        int location=arr[minIndex];
        for(int i=minIndex;i<=maxIndex;i++)
        {
            if(location<arr[i])
            {
                location=arr[i];
            }
            result+=location;
        }
        if(location>arr[maxIndex])
        {
            int al=maxIndex;
            while(true)
            {
                if(location==arr[al]) //10을 만날때 stop!
                {
                    break;
                }
                else
                {
                    if(arr[al]>arr[maxIndex]) //웅덩이 방지 !!
                    {
                        result-=(location-arr[al]);
                        arr[maxIndex]=arr[al];
                    }
                    else // 10 10 10 10에서 남는 곳만큼 빼야한다
                    {
                        result-=(location-arr[maxIndex]);
                    }
                }
                al--;
            }
        }
        System.out.println(result);
    }
}