KLIS 질문입니다.

  • kun452
    kun452

    안녕하세요
    문제를 풀다가 오답이 떠서 질문드립니다.
    문제에서 cnt배열은 index에서 시작되는 lis의 갯수를 가지고 있고
    long_max 배열은 index에서 시작되는 최대 연속 수의 갯수를 담고있습니다.
    그리고 reconstruct는 각각 뒤에서부터 skip보다 작으면 앞의것을 선택하는 방식으로 구현해봤는데 오답으로 뜨네요.
    제가 푼 방식이 아에 잘못된 건가요?

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    struct value{
        int vale; // long_max
        int num; // cnt 갯수
    };
    
    void reconstruct(int start, int skip, vector<int>& lis, int *A, int n, int *long_max, int *cnt, int llong) {
        vector <value> *B = new vector <value>[llong+1];
        value a;
    
        for(int i=0; i<n; i++){
            a.vale = A[i];
            a.num = cnt[i];
    
            B[long_max[i]].push_back(a);
        }
    
        int *poin = new int[llong+1];
    
        for(int i=1; i<llong+1; i++){
            poin[i] = B[i].size()-1;
        }
    
        a.num = 0;
        a.vale = 0;
        int index = llong;
        while(index != 0){
            if(a.vale > B[index][poin[index]].vale){
                poin[index]--;
                continue;
            }
    
            a = B[index][poin[index]];
            if(a.num < skip){
                while(skip > a.num){
    
                    skip = skip - a.num;
                    poin[index]--;
                    a = B[index][poin[index]];
                }
            }
    
            lis.push_back(a.vale);
            index--;
        }       
    
    }
    
    int main(){
        int num;
        cin >> num;
    
        for(int i=0; i<num; i++){
            int n, K;
    
            cin >> n >> K;
    
            int *A = new int[n];
            int *long_max = new int[n];
            int *cnt = new int[n]; // index번호에서 시작되는 단조함수의 갯수
            int llong = 0;
    
            for(int j=0; j<n; j++){
                cin >> A[j];
                long_max[j] = 1;
            }
    
            for(int j=n-1; j>=0; j--){
                for(int k=n-1; k>=j; k--){
                    if(A[j] < A[k] && long_max[k] >= long_max[j]){
                        long_max[j] = long_max[k] + 1; // 4 4 3 3 2 2 1 1 로 생김
                    }
    
                    if(llong < long_max[j])
                        llong = long_max[j];
                }
            }
    
            for(int j= n-1; j>=0; j--){
                if(long_max[j] == 1){
                    cnt[j] = 1;
                    continue;
                }
    
                vector <int> qp;
    
                int num = 1;
                int last = 0;
    
                for(int k=j+1; k<n; k++){
                    if(long_max[j] <= long_max[k])
                        continue;
    
                    if(last == long_max[k]){
                        num++;
                    }
                    else{
                        qp.push_back(num);
                        last = long_max[k];
                        num = 1;
                    }   
                }
    
                qp.push_back(num);
                cnt[j] = 1;
                while(!qp.empty()){
                    int np = qp.back();
                    cnt[j] = cnt[j] * np;
                    qp.pop_back();
                }
    
            }
    
    
            vector<int> kth;
            reconstruct(0, K, kth, A, n, long_max, cnt, llong);
            cout << kth.size() << endl;
            for(int i = 0; i < kth.size(); i++) {
                if(i) cout << ' ';
                cout << kth[i];
            }
            cout << endl;
    
    
        }
    
        return 0;
    }
    

    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    힌트: cnt에 들어가는 최대 값이 얼마일지 생각해 보세요~


    9년 전 link
  • kun452
    kun452

    아.. 감사합니다~


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