[알고리즘 문제해결전략] FENCE - 울타리 잘라내기

[생각의 흐름]

1. 모든 경우의 수 중 가장 넓은 사각형의 넓이를 구하려고 시도 => N^2으로 시간초과 발생 

2. 분할정복을 시도

3. 가운데 사각형을 기준으로 1)왼쪽 전체 사각형 2)오른쪽 전체 사각형 3)가운데 포함 좌우 사각형 추가하는 세가지 경우로 나눔

4. 가운데 포함 좌우 사각형의 경우 좌,우를 선택할 때 높이가 더 높은 사각형부터 추가함 => 작은 사각형을 먼저 추가하면 최대 값을 구할 수 없는 경우가 생김

 

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

#include <stdio.h>
#include <algorithm>
#include <string.h>

const int MAX_FENCE = 20002;
using namespace std;

int N;
int fenceHeight[MAX_FENCE];
int highestFence;

int getLowestHeight(int a, int b)
{
    int lowestHeight = 10000;
    for (int i = a; i <= b; i++)
    {
        lowestHeight = min(lowestHeight, fenceHeight[i]);
    }

    return lowestHeight;
}

int calculateMaxArea(int a, int b)
{
    int lowestHeight = getLowestHeight(a, b);
    return (b - a + 1) * lowestHeight;
}

int sol(int bottom, int top)
{
    if (bottom == top)
        return fenceHeight[bottom];

    int mid = (top + bottom) / 2;

    int leftIdx, rightIdx;
    int ret = fenceHeight[mid];
    leftIdx = rightIdx = mid;

    // mid
    while (leftIdx > bottom || rightIdx < top)
    {
        if (leftIdx > bottom && rightIdx < top)
        {
            if (fenceHeight[leftIdx - 1] > fenceHeight[rightIdx + 1])
            {
                leftIdx--;
                ret = max(ret, calculateMaxArea(leftIdx, rightIdx));
            }
            else
            {
                rightIdx++;
                ret = max(ret, calculateMaxArea(leftIdx, rightIdx));
            }
        }
        else
        {
            if (leftIdx > bottom)
            {
                leftIdx--;
                ret = max(ret, calculateMaxArea(leftIdx, rightIdx));
            }
            if (rightIdx < top)
            {
                rightIdx++;
                ret = max(ret, calculateMaxArea(leftIdx, rightIdx));
            }
        }
    }

    // left
    ret = max(ret, sol(bottom, mid));
    // right
    ret = max(ret, sol(mid + 1, top));

    return ret;
}

int main(void)
{
    int C;
    scanf("%d", &C);

    for (int tc = 0; tc < C; tc++)
    {
        scanf("%d", &N);
        highestFence = 0;
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &fenceHeight[i]);
        }
        printf("%d\n", sol(0, N - 1));
    }

    return 0;
}