# [Platinum V] Jump Jump Championship [문제 링크](https://www.acmicpc.net/problem/1974) ## 문제 설명 <p>후연 조교는 2007년 황금 돼지해(확실치 않음)를 맞이하여 Jump Jump Championship에 참가하였다. 이 대회에서는 아래와 같은 규정으로 우승자를 가린다.</p> <p>우선 점프대가 N개 있는데, 원하는 아무 한 곳 점프대에서 출발하여 오른쪽으로만 진행하면서 점프대에 놓여있는 트로피를 가장 많이 주워야 한다. 단, 트로피를 가져올 때의 조건은 아래와 같다:</p> <ol> <li>첫 점프대의 트로피는 그냥 가져갈 수 있다.</li> <li>첫 번째 이후 도달하는 점프대에 놓인 트로피를 가져가기 위해서는 이전에 있었던 점프대에서 주워온 트로피를 넣을 수 있어야 한다. 즉 이전에 얻은 트로피의 크기가 더 작아야 한다. 작은 트로피를 넣었으면, 이제 큰 트로피를 들고, 다른 점프대로 이동하여 마찬가지로 반복한다. (혹은 이동할 곳이 없으면 끝난다)</li> <li>트로피를 가져가지 않으면서 다른 점프대로 이동할 수 없다.</li> </ol> <p>예를 들어 점프대가 5개 있고, 트로피의 크기가 3 2 4 2 5와 같이 놓여 있다면, 2번 점프대 → 3번 점프대 → 5번 점프대로 이동하여 (2 4 5)의 트로피 3개를 얻을 수 있다. 혹은 1번 점프대 → 3번 점프대 → 5번 점프대의 경우도 가능하다.</p> <p>당신은 후연 조교를 도와서 후연 조교가 최대 몇 개의 트로피를 얻을 수 있는지, 또 어떤 방법으로 얻을 수 있는지 알아내야 한다.</p> ## 입력 <p>첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스에 대해서는 점프대의 수 N(1 ≤ N ≤ 10,000)과 각 점프대에 놓인 트로피들의 크기가 주어진다. 크기가 같은 트로피가 있을 수 있으며 트로피의 1부터 100만 이하의 자연수이다.</p> ## 출력 <p>각 테스트 케이스에 대해 첫 줄에 후연 조교가 얻을 수 있는 최대 트로피의 수를 출력하고, 둘째 줄에는 이동한 점프대의 경로를 출력한다. 여러 가지가 있을 경우 아무거나 한 가지를 출력한다.</p> ## 풀이 #### LIS를 이분탐색을 사용하여 NlogN 안에 구하면 되는 문제였다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 10'000; int prv[MAX], val[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; memset(prv, 0, sizeof prv); vector<int> lis; for(int i=1;i<=n;i++) { cin >> val[i]; if(lis.empty() || val[lis.back()]<val[i]) { if(!lis.empty()) prv[i] = lis.back(); lis.push_back(i); } else { int left=0, right=lis.size()-1; while(left<right) { int mid = (left+right)/2; if(val[lis[mid]]<val[i]) left=mid+1; else right=mid; } if(left!=0) prv[i] = lis[left-1]; lis[left] = i; } } cout << lis.size() << '\n'; stack<int> stk; for(int i=lis.back();i!=0;i=prv[i]) stk.push(i); while(!stk.empty()) { cout << stk.top() << ' '; stk.pop(); } cout << '\n'; } } ```