이번에 분할정복에 대해서 공부하는 평범한 대학생입니다. ^;;
FENCE문제가 쉽다고 하길래 풀어봤는데 도무지 오답에 대한 테스트 케이스를 찾지 못해서 이틀째 고생중이네요. ㅠㅠ

처음에는 책에도 살짝 언급되어있는 '무식하게 풀기' 방법을 통해서 문제를 접근했는데 당연하게도 O(N^2)의 시간이 Timeout을 내보내더라구요. ㅠㅠ

그래서 분할정복을 적용시켜서, left와 right의 중간에 pivot을 잡고, 그 pivot값을 기준으로 left, right를 분할시켜서 문제를 시도했습니다. pivot은 left와 right 로 명시된 값의 범위 중에서 가장 작은 값 인덱스를 잡았습니다.

즉, 범위 내에서 최소 높이를 기준으로 left와 right을 나눠서 각각의 부분해를 찾고, 합친 다음에 최소높이 * 범위 만큼의 부분해와 비교해서 큰 값을 리턴하는 알고리즘입니다.

테스트 케이스에 0을 대입한 경우 등 거의 50개가량 추가로 테스트를 해봤는데 답이 잘 나오는데, 오답이 뜨네요 ㅋㅋ 시간은 초과하지 않는것 같은데...
제 알고리즘 좀 봐주실 수 있나요? ㅠㅜ

#include <iostream>
#include <string>

using namespace std;

static int N = 0;
static int* blockHeights = nullptr;

int Fence(int left, int right){
    int volume = 0;
    int ret = 0;
    int min_height = 10001;
    int pivot = 0;

    if(left>=right){
        return blockHeights[left];
    }
    for(int i=left; i<right; i++){
        if(blockHeights[i]<min_height){
            min_height = blockHeights[i];
            pivot = i;
        }
    }
    volume = (right-left) * min_height;

    ret = Fence(left, pivot);
    if(volume < ret)
        volume = ret;
    ret = Fence(pivot+1, right);
    if(volume < ret)
        volume = ret;
    return volume;
}
int main(void){
    int C = 0;
    int caseCnt = 0;
    int* resultArr = nullptr;

    cin>>C;
    resultArr = new int[C];

    while(caseCnt < C){
        int val = 0;
        cin>>N;
        blockHeights = new int[N];
        for(int i=0; i<N; i++)
            cin>>blockHeights[i];

        val = Fence(0, N);
        resultArr[caseCnt] = val;
        delete[] blockHeights;
        caseCnt++;
    }

    for(int i=0; i<caseCnt; i++)
        cout<<resultArr[i]<<endl;
    return 0;
}