KLIS를 풀다가 RTE가 떴는데요

  • KimJJ
    KimJJ

    계속 오답만 뜨길래 K가 존재하는 LIS의 갯수보다 많은 경우도 있을까 싶어서 한번 exit(1)을 넣어봤더니 RTE가 나오네요.

    그렇지만 제가 뭔가 잘못 짠 건지도 모르겠습니다. 확인 부탁드릴게요.

    #include<iostream>
    #include<algorithm>
    #include<utility>
    #include<vector>
    #include<cstdlib>
    using namespace std;
    
    const int INF = 1000001;
    vector< int > D, Lis, Cnt;
    vector< vector< pair<int, int> > > Back;
    int K, last;
    void input(){
        int N;
        cin >> N >> K;        
        // 맨 앞에 가장 작은 수를, 맨 뒤에 가장 큰 수를 넣음으로써 추적이 편하게 함.
        D.push_back(0);
        for(int i=1;i<=N;++i){
            int num;
            cin >> num;
            D.push_back(num);
        }
        D.push_back(INF);    
    }
    void BackTrack(int pos){
        int i;
        if(pos == last) return;
        if(pos != 0) cout << D[pos] << " ";
        for(i=0;i<Back[pos].size(); ++i){
            const int nextPos = Back[pos][i].second;
            if(Cnt[nextPos] < K) K -= Cnt[nextPos];
            else {
                BackTrack(nextPos);        
                return;
            }
        }
        // 여기에 도달한다면 K번째 수열이 존재하지 않음!
        exit(1);
    }
    int main(){
        int C;
        cin >> C;
        while(C--){
            D.clear();
            input();
    
            int i, j;
            // Lis[i] : D[i]로부터 시작하는 LIS의 길이
            Lis = vector<int>(D.size(), 0);
            last = D.size()-1;
            for(i=last-1; i>=0; --i){
                for(j = i + 1; j<= last; ++j){
                    if(D[i] > D[j]) continue;
                    if(Lis[i] < Lis[j] + 1){
                        Lis[i] = Lis[j] + 1;
                    }
                }            
            }
    
            Cnt = vector<int>(D.size(), 0);
            Back.resize(D.size());
            Cnt[last] = 1;
    
            // Cnt[i] : D[i]로부터 시작하는 LIS의 개수
            //Back[i] : [D[i], D[j], ... ] 가 LIS가 되는 D[j]의 위치(D[j] 기준으로 오름차순 정렬!)
            for(i=last-1; i >= 0; --i){
                Cnt[i] = 0;
                Back[i].clear();
                for(j = i + 1; j <= last; ++j){
                    if(D[i] > D[j]) continue;
                    if(Lis[i] == Lis[j] + 1){
                        Cnt[i] += Cnt[j];
                        Back[i].push_back(make_pair(D[j], j));
                    }
                }                        
                sort(Back[i].begin(), Back[i].end());
            }
    
            cout << Lis[0] - 1 << endl;
            BackTrack(0);
            cout << endl;
        }
        return 0;
    }
    ~~~

    11년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    힌트: LIS의 수는 최대 몇 개나 될까요?


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