FENCE문제 TLE가 계속 뜹니다...

  • cjdahrl
    cjdahrl
    #include <iostream>
    #include <vector>
    #include <ctime>
    
    using namespace std;
    
    void FENCE();
    int Area(int left, int right, vector<int> vtr);
    int maximum(int a, int b);
    int minimum(int a, int b);
    
    int main() {
        int nTestCase;
    
        cin >> nTestCase;
    
        while (nTestCase--) {
            //int start = clock();
            FENCE();
            //int end = clock();
            //double time = (double)(end - start);
            //cout << "Access Time : " << time / CLOCKS_PER_SEC << endl;
        }
        return 0;
    } // main()
    
    void FENCE() {
        int nFence;
        int nHeight;
        vector<int> vtrInput;
    
        cin >> nFence;
    
        //srand((unsigned)time(NULL));
    
        while (nFence--) {
            //테스트케이스 입력
            cin >> nHeight;
            //테스트케이스 생성
            //nHeight = rand()%10000;
            //cout << nHeight << " ";
            vtrInput.push_back(nHeight);
        }
        //cout << endl <<  "MAXIMUM AREA : ";
        cout << Area(0, vtrInput.size() - 1, vtrInput) << endl;
        vtrInput.clear();
    } // FENCE()
    
    int Area(int nLeft, int nRight, vector<int> nVtrHeight) {
        // 좌극 == 우극일때 높이를 반환
        if (nLeft == nRight) return nVtrHeight[nLeft];
        // 중간 경계면을 기준으로 분할
        int nMid = (nLeft + nRight) / 2;
        int nMaxOne = maximum(Area(nLeft, nMid, nVtrHeight), Area(nMid + 1, nRight, nVtrHeight));
        // 중간 경계면을 포함하는 넓이를 계산
        int nLow = nMid;
        int nHigh = nMid + 1;
        int nHeight = minimum(nVtrHeight[nLow], nVtrHeight[nHigh]);
        // 좌우값 중 큰값과 경계면을 포함하는 두펜스의 넓이 중 큰 값을 저장
        nMaxOne = maximum(nMaxOne, nHeight * 2);
        // 경계면을 좌극값과 우극값 사이에서 확장
        while (nLeft < nLow || nHigh < nRight) {
            // 우측으로 확장할 공간이 있고 &&
            // ( 좌측으로 확장할 공간이 없거나 || 우측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )
            if (nHigh < nRight && (nLow == nLeft || nVtrHeight[nLow - 1] < nVtrHeight[nHigh + 1])) {
                // 우측으로 확장
                ++nHigh;
                // 확장한면에서 가장 낮은 높이값을 저장
                nHeight = minimum(nHeight, nVtrHeight[nHigh]);
            }
            // 좌측으로 확장할 공간이 있고 &&
            // ( 우측으로 확장할 공간이 없거나 || 좌측으로 확장하는 경우에 더 큰 높이값을 가져가는 경우 )
            else {
                // 좌측으로 확장
                --nLow;
                nHeight = minimum(nHeight, nVtrHeight[nLow]);
            }
            // (좌우값 중 큰값과 경계면을 포함하는 두 펜스의 넓이중 큰값) 과 경계면을 포함하는 면의 넓이중에 큰값을 저장
            nMaxOne = maximum(nMaxOne, nHeight*(nHigh - nLow + 1));
        }
        return nMaxOne;
    } // maximumArea()
    
    // 큰값을 반환
    int maximum(int a, int b) {
        if (a > b) return a;
        else return b;
    } // max()
    
    // 낮은값을 반환
    int minimum(int a, int b) {
        if (a < b) return a;
        else return b;
    } // min()
    

    책에 있는 알고리즘을 이용해서 풀었는데 TLE가 뜨네요
    시간계산해보니 입력값이 20000개 일때 평균 6~9초정도 걸리는데 어느부분을 수정해야할까요?


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

    테스트케이스 생성부분에 cout 부분을 주석처리 해버리니까 입력값 2만개 0.8초 내로 처리되네요... 뭐가 문젠지 여전히 모르겠습니다...


    10년 전 link
  • hana5505
    hana5505

    cout이 느립니다. 그러니까 printf를 써보세요.


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