FENCE문제 질문있습니다. 왜 오답인지 도무지 모르겠네요. ㅠ

  • Jinsanger
    Jinsanger

    이번에 분할정복에 대해서 공부하는 평범한 대학생입니다. ^^;;
    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;
    }
    

    10년 전
2개의 댓글이 있습니다.
  • Being
    Being

    Fence(0, N)에서 pivot을 맨 마지막 원소를 잡으면 어떻게 될지 생각해 보시기 바랍니다.


    10년 전 link
  • Jinsanger
    Jinsanger

    최근에 시험기간이라 바빠서 늦게 봤네요. ㅋㅋ
    그부분만 수정하니까 바로 정답뜨더군요~!! 감사합니다.
    꼼꼼한 성격이 아니라 이런 실수가 잦네요.ㅎㅎ


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.