FENCE

https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

각각의 높이가 다른 울타리에서 최대 넓이의 직사각형을 찾는 문제이다. 여러 방법으로 풀 수 있지만 여기서는 분할 정복으로 풀어보도록 하자. 전체 판자를 절반으로 나눈다고 하자. 그러면 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나에 속한다.

 

1. 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.

2. 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.

3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐져 있다.

 

1,2번은 전체 문제를 반으로 나눈 부분 문제를 재귀 호출하여 해결할 수 있다. 3번의 경우만 고려하면 된다. 먼저 3번의 경우 분할한 기준으로부터 인접한 왼쪽, 오른쪽 판자는 무조건 포함한다는 것을 알 수 있다. 그리고 양 옆을 비교해서 높이가 더 높은 판자쪽으로 확장해가면서 넓이를 갱신해주면 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int h[20005];

int solve(int left,int right)
{
    if(left==right) return h[left];
    int mid=(left+right)/2;
    int ret=max(solve(left,mid),solve(mid+1,right));
    int low=mid,high=mid+1;
    int height=min(h[low],h[high]);
    ret=max(ret,height*2);
    while(left<low || high<right)
    {
        if(high<right && (low==left || h[low-1]<h[high+1]))
            height=min(height,h[++high]);
        else
            height=min(height,h[--low]);
        ret=max(ret,height*(high-low+1));
    }
    return ret;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&h[i]);
        printf("%d\n",solve(0,n-1));
    }
    return 0;
}