[분할 정복, 스위핑, 스택, 상호 배타적 집합] FENCE 울타리 잘라내기

#include <iostream>
#include <cstdio>
 
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
 
int fenceHeight[20000] ={0,};
 
int maxRec(int low ,int high)
{
    int ret = 0, mid = (low + high)/2, left = 0, right = 0, tmpRec = 0, width = 1, height = 0;
 
    if(low +1 == high)
        return fenceHeight[low];
 
    ret  = max(maxRec(low, mid),maxRec(mid, high));
 
    left = mid - 1; right = mid + 1; height = fenceHeight[mid];
    
    while(left >= low || right < high)
    {
        width++;
        if(left < low || ((right != high) && (fenceHeight[right] > fenceHeight[left]))) 
        {
            height = min(height, fenceHeight[right]);
            right++;
        }
        else
        {
            height = min(height, fenceHeight[left]);
            left--;
        }
        tmpRec = max(tmpRec, width*height);
    }
    ret = max(ret, tmpRec);
    
    return ret;
}
 
int main(void)
{
    int testCase{0}, fenceNum{0};
    scanf("%d", &testCase);
    for(int i{0}; i < testCase; i++)
    {
        scanf("%d",&fenceNum);
        for(int j{0}; j < fenceNum; j++)
        {
            scanf("%d",&fenceHeight[j]);
        }
        printf("%d\n",maxRec(0, fenceNum));
    }
}

 

1. 문제를 더 작은 문제로 분할하는 과정

    이 문제는 다음과 같이 분할하여 답을 구할 수 있다.

    1. 전체 울타리 절반의 왼쪽에 최대 크기를 가질경우

    2. 전체 울타리 절반의 오른쪽에 최대 크기를 가질경우

    3. 중간 울타리를 가지는 직사각형이 최대 크기를 가질경우

    함수는 울타리 개수가 n일 때 n번 실행된다.

    기저 사례가 너비가 1일때 이기 때문.

2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정

    각 분할된 문제 한단계에서 왼쪽, 오른쪽 크기를 비교하여

    큰것을 중간을 거치는 크기와 비교한다.

    이 때 걸리는 시간은 while문에 지배된다. 

    while문은 각 단계에서 n 번 실행된다

    그리고 단계의 깊이는 lgn 이므로

    총 nlgn 시간이 걸린다.

 

3. 기저 사례

    기저사례는 너비가 1일때 해당 높이를 리턴한다. 

 

 

4. 시간을 더 줄일 수 있는지? 다른 풀이 방법은 있는지?

 

    스위핑 기법과 스택을 결합하면 선형시간안에 문제를 해결할 수 있다고 한다. (n)

    상호 배타적 집합을 이용하여 문제를 해결할 수 있다고 한다. (nlgn)

 

FENCE