KLIS 질문입니다. 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 힌트: cnt에 들어가는 최대 값이 얼마일지 생각해 보세요~ 9년 전 link kun452 아.. 감사합니다~ 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kun452
안녕하세요
문제를 풀다가 오답이 떠서 질문드립니다.
문제에서 cnt배열은 index에서 시작되는 lis의 갯수를 가지고 있고
long_max 배열은 index에서 시작되는 최대 연속 수의 갯수를 담고있습니다.
그리고 reconstruct는 각각 뒤에서부터 skip보다 작으면 앞의것을 선택하는 방식으로 구현해봤는데 오답으로 뜨네요.
제가 푼 방식이 아에 잘못된 건가요?
9년 전