히스토그램에서 가장 큰 직사각형 C++ - 백준 6549

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

이 문제는 태그나 답지 도움 없이는 쉽게

접근 할 수 없는 문제이다.

더 많은 경험을 하는 것이 문제풀이에 도움이 될 것 같다.

문제 접근

히스토그램에서 가장 큰 직사각형이 존재하는 경우는 3가지이다.

중심으로 두개의 영역을 나눴을때

1. 왼쪽에 존재하는 경우
2. 오른쪽에 존재하는 경우
3. 중심에 겹치면서 존재하는 경우

이렇게 3가지로 나눌 수 있다.

왼쪽과 오른쪽에 존재하는 경우는 재귀적인 방식(분할 정복)으로 처리해주면

된다.

하지만 중심에 겹치면서 존재하는 경우는 다소 까다롭게 느껴진다.

직사각형의 넓이는 직사각형을 이루고 있는 막대들의 길이 중

최소 길이 $\cdot$ 밑변 길이 가 된다.

히스토그램 중심에 있고, 밑변의 길이가 1인 히스토그램 막대가 존재한다고 하자.

히스토그램의 길이를 점차 늘려가며 탐색할 것인데

(자명히 중심에 겹치면서 존재하는 경우를 살펴봐야하기 때문이다.)

히스토그램의 넓이를 넓히려면 추가하는 막대의 높이가

현재 높이를 유지하거나 현재 높이보다 커질 때가 최적의 답이다.

왜냐하면 최소 길이 $\cdot$ 밑변 길이 이기 때문이다.

따라서 더 높은길이의 막대를 선택하여 해당 구간에 존재하는

될 수 있는 직사각형의 넓이를 탐색하면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

ll a[100001];

ll solve(int l, int r){
    if(l==r) return a[l];
    int mid=(l+r)/2;
    ll s=(l+r)/2,e=s+1;
    ll curh;
    if(a[s]>a[e]){
        curh=a[s];
        e--;
    }
    else{
        curh=a[e];
        s++;
    }
    ll tmp=curh;
    while(s!=l || e!=r){
        if(s==l || e==r){
            if(s==l){
                e++;
                curh=min(curh,a[e]);
            }
            else{
                s--;
                curh=min(curh,a[s]);
            }
            tmp=max(tmp,curh*(e-s+1));
            continue;
        }
        if(a[s-1]>a[e+1]){
            s--;
            curh=min(curh,a[s]);
            tmp=max(tmp,curh*(e-s+1));
        }
        else{
            e++;
            curh=min(curh,a[e]);
            tmp=max(tmp,curh*(e-s+1));
        }
    }
    return max(tmp,max(solve(l,mid),solve(mid+1,r)));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // freopen("in","r",stdin);
    int n;
    while(1){
        cin >> n;
        if(n==0) break;
        for(int i=0;i<n;i++) cin >> a[i];
        cout << solve(0,n-1) << '\n';
    }
    return 0;
}