[JAVA]백준 1725번: 히스토그램

www.acmicpc.net/problem/1725

1725번: 히스토그램

 

1. 문제 설명

 

주어진 히스토그램에 대해 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하는 문제이다.

 

종만북의 분할 정복 예시 문제 울타리 잘라내기 문제와 같은 문제이다.

 

종만북의 풀이과정 같이 3가지의 형태로 문제를 분할하여서 풀었다.

 

막대그래프를 반으로 잘랐을 때 가장 큰 직사각형은 3가지의 경우로 존재할 수 있다.

 

1. 가장 큰 직사각형은 왼쪽 그래프에만 있을 경우

2. 가장 큰 직사각형은 오른쪽 그래프에만 있을 경우

3. 가장 큰 직사각형은 중앙에 걸쳐있을 경우

 

1번과 2번은 그래프를 반으로 나누어서 함수를 재귀 호출해서 얻는다.

 

3번은 중앙에 걸쳐있는 것을 가정하기에 lo=mid, hi=mid+1인 너비가 2인 직사각형에서부터 시작한다.

 

그리고 더 높이가 큰 쪽을 먼저 선택하면서 lo가 left, hi가 right가 될 때까지 사각형을 확장하면서 최댓값을 구한다.

 

2. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int num;

    public static int[] list=new int[100001];

    public static void main(String[] args) throws IOException {
        Scanner scan=new Scanner(System.in);

        num=scan.nextInt();

        for(int x=0;x<num;x++)
            list[x]=scan.nextInt();


        System.out.println(divide(0,num-1));


    }

    public static int divide(int left,int right){
        if(left==right)
            return list[left];
        else{
            int mid=(left+right)/2;

            int max_value=Math.max(divide(left,mid),divide(mid+1,right));

            int min_height=Math.min(list[mid],list[mid+1]);
            int temp_max_value=2*min_height;

            int lo=mid;
            int hi=mid+1;

            while(lo>left || hi < right){
                if(lo==left || list[hi+1]>list[lo-1]){
                    hi++;
                    min_height=Math.min(min_height,list[hi]);
                }else{
                    lo--;
                    min_height=Math.min(min_height,list[lo]);
                }

                temp_max_value=Math.max(temp_max_value,(hi-lo+1)*min_height);
            }

            return Math.max(max_value,temp_max_value);
        }
    }


}