[백준] 6549번(Java)

📖 히스토그램에서 가장 큰 직사각형

[ 문제 ]
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

💡풀이

• 분할 정복 카테고리에 있는 문제니 분할 정복으로 풀어보고자 백방으로 노력했다.
• 히스토그램을 절반 나누어서 각 반쪽 도형 내에 포함된 최대 넓이의 사각형과, 가운데 기준선을 포함한 사각형의 넓이를 비교해 최대를 구하는 방식으로 진행했다.
• 분할 정복의 적용 자체는 어렵지 않았는데 아이디어 떠올리는게 어려웠다...

package divconqur;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bj6549 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    public static void main(String[] args) throws IOException {
        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            if(n == 0) break;

            long[] histogram = new long[n];

            for(int i = 0 ; i < n ; i ++){
                histogram[i] = Integer.parseInt(st.nextToken());
            }
            long answer = divcon(0, n - 1, histogram);
            System.out.println(answer);
        }
    }
    private static long divcon(int start, int end, long[] arr){
    	// 히스토그램 막대기 한 개일 경우 그대로 반환
        if(start == end){
            return arr[start];
        } else{
            int mid = (start + end) / 2;
            
            // 왼쪽 히스토그램 절반에서의 최대 사각형 vs 오른쪽 히스토그램의 최대 사각형 비교
            long lrmax = Math.max(divcon(start, mid, arr), divcon(mid+1, end, arr));

            int ts = mid;
            int te = mid;
            long base = arr[mid];
            long mmax = 0;

			// 가운데 기준선을 포함하는 사각형 큰 거 하나 확인
            while(start < ts && te < end){
                if(arr[te + 1] >= arr[ts - 1]){
                    te += 1;
                    base = Math.min(base, arr[te]);
                } else {
                    ts -= 1;
                    base = Math.min(base, arr[ts]);
                }
                mmax = Math.max(mmax, base * (te - ts + 1));
            }

			// 위의 while문에서 한 쪽 끝에만 도달했으니, 남은 부분을 탐색하는 과정 필요
            while(ts > start){
                ts -= 1;
                base = Math.min(base, arr[ts]);
                mmax = Math.max(mmax, base * (te - ts + 1));
            }

            while(te < end){
                te += 1;
                base = Math.min(base, arr[te]);
                mmax = Math.max(mmax, base * (te - ts + 1));
            }

            return Math.max(mmax, lrmax);
        }
    }

}

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