[틀림] 백준 LIS 5 // 원복 LIS

https://www.acmicpc.net/problem/14003

* 풀이

• 각 숫자에 대해
• ans[ ] 에 {idx, num}을 저장 해 놓는게 키포인트
• 이후 뒤부터 탐색
  • pos=len-1일때 stack에 넣기
• 스택에 넣고빼면 역순출력 완성

• 헤맸던 부분
  • lower_bound 대상은 lis임. a가 아님
  • lower_bound 범위는 (lis, lis+len임). lis + n이 아님
  • 초기화는 max+1로 초기화 (역시 lis가 대상. a 가 아님)

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int len, n;
ll a[1000000+4];
ll lis[1000000+4];
pair<int,int> ans[1000000+4]; // pos,num

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   fill(lis,lis+1000000+4,1000000000+1); // lis를 초기화 : max+1
   cin>>n;
   for(int i=0;i<n;++i) {
      cin>>a[i];
   }

   for(int i=0;i<n;++i) {
      int idx = lower_bound(lis,lis+len,a[i])-lis; // a가 아니라 lis가 탐색대상!
      if(idx==len) {
         len++;
      }
      lis[idx]=a[i];
      ans[i].first = idx;
      ans[i].second = a[i];
   }
   cout<<len<<"\n";

   stack<int> s;
   for(int i=n-1;i>=0;--i) {
      if(ans[i].first == len-1) {
         s.push(ans[i].second);
         len--;
      }
   }
   while(s.size()) {
      cout<<s.top()<<" ";
      s.pop();
   }
}