KLIS를 풀다가 RTE가 떴는데요 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 힌트: LIS의 수는 최대 몇 개나 될까요? 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
KimJJ
계속 오답만 뜨길래 K가 존재하는 LIS의 갯수보다 많은 경우도 있을까 싶어서 한번 exit(1)을 넣어봤더니 RTE가 나오네요.
그렇지만 제가 뭔가 잘못 짠 건지도 모르겠습니다. 확인 부탁드릴게요.
11년 전