[백준] 가장 긴 증가하는 부분 수열 5(14003)

문제 링크 : [백준] 가장 긴 증가하는 부분 수열 5(14003)

문제 설명

수열이 주어졌을 때, LIS 길이와 구성 요소들을 출력하세요.

입력

N(수열 원소 갯수, 1 <= N <= 1,000,000)
A_i(원소의 값, -1,000,000,000 <= A_i <= 1,000,000,000)

6
10 20 10 30 20 50

출력

LIS의 길이와 구성 요소

4
10 20 30 50

카테고리

#LIS #DP

시간 복잡도 상한

O(NlogN)

해결 방법

1. 증가하는 최장 부분수열 LIS를 구하면 되는 문제입니다.
2. 단 NlogN LIS를 구할 경우, LIS를 구성하는 원소를 알 수 없어서 다른 장치가 필요합니다.
3. LIS의 동작 원리를 생각해보면, lower_bound를 이용하여 위치를 찾아갈 때, 자신의 앞 위치는 항상 정확하게 찾을 수 있음을 알 수 있습니다.
4. 따라서 lower_bound로 위치를 찾아가면서 앞 요소의 링크들을 저장하는 배열을 만듭니다.
5. LIS 마지막 원소는 항상 가장 긴 원소의 마지막 요소이므로, 역추적하여 LIS 연결 요소들을 찾습니다.

시간복잡도

O(NlogN)

코드

#include<cstdio>
#include<vector>
using namespace std;
int n,d[1000000],p[1000000]={1},i,x,y,s[100000];
vector<int>v;
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",d+i);
    v.push_back(d[0]);
    for(i=1;i<n;i++){
        if(v[v.size()-1]<d[i])v.push_back(d[i]),p[i]=v.size();
        else {
            x=lower_bound(v.begin(),v.end(),d[i])-v.begin();
            v[x]=d[i];
            p[i]=x+1;
        }
    }
    printf("%d\n",v.size());
    for(y=v.size(),i=n-1;i>=0;i--)if(p[i]==y)s[--y]=d[i];
    for(i=0;i<v.size();i++)printf("%d ",s[i]);
}