Algorithm/이분탐색
[틀림] 백준 LIS 5 // 원복 LIS
Mini_96
2025. 3. 12. 13:39
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();
}
}