BOJ 1725 히스토그램

문제

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

히스토그램에서 최대 넓이의 직사각형을 찾는 문제이다.

 

풀이

i부터 j까지 선택을 하면 \( (j-i+1)\times min({A[i], …, A[j]}) \)  가 넓이가 된다.

(s, e)의 답을 구하기 위해서 (s, mid), (mid+1, e) 의 답은 재귀로 구하고, 왼쪽 부분문제와 오른쪽 부분문제에 걸쳐 있는 답만 구하자.

처음에는 mid, mid+1만 포함되어 있는 직사각형을 만들고, 좌우로 한칸씩 늘려가며 선택하며 답을 구한다.

 

답은 양 끝에서 더 큰 쪽으로 확장시켜 나가는 것이다.

물론 이 방법은 각 단계에서 최적의 선택을 해 나가는 그리디이다.

그리디 -> 증명 -> 귀류법 (!)

 

 

위 그림에서 그리디 알고리즘으로 선택한 직사각형보다 더 최적해 빨간색 직사각형이 있다고 가정하자. 

그리디로 선택할 때 길이를 하나씩 늘려 나가기 때문에 빨간색 직사각형과 동일한 너비의 직사각형이 존재한다.

또한, 너비는 같은데 넓이는 작아야 하니, 높이는 초록색 직사각형이 더 낮으며, 그 높이를 만드는 판자 X가 존재한다.

물론, 빨간색 직사각형은 당연히 모두 X보다 높이가 더 크다.

그렇다면, 그리디 알고리즘은 X를 선택하기 위해서는 그 왼쪽에 X이하의 판자가 존재했어야 가능하다.

그러나, 이는 빨간색 직사각형의 모든 판자는 X보다 크다는 것에 모순이 발생. 즉, 그리디 알고리즘은 성립한다.

 

이 문제도 D&C 구현에 익숙해 지도록 하자.

시간복잡도 : $O(NlogN)$ (머지소트와 똑같음)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define MAXN 100000

int n;
ll arr[MAXN+10];

ll solve(int s, int e)
{
    if(s==e) return arr[s];

    int mid = (s+e)/2;
    ll ret = max(solve(s, mid), solve(mid+1, e));

    int l = mid, r = mid+1;
    ll minval = min(arr[mid], arr[mid+1]);
    ret = max(ret, 2*minval);

    while(s<l || r<e)
    {
        if(r<e && (s==l || arr[l-1]<arr[r+1]))
        {
            r++;
            minval = min(minval, arr[r]);
        }
        else
        {
            l--;
            minval = min(minval, arr[l]);
        }
        ret = max(ret, minval*(r-l+1));
    }
    return ret;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%lld", &arr[i]);
    printf("%lld\n", solve(1, n));

    return 0;
}