가장 긴 증가하는 부분 수열 5

이전에 풀었던 가장 긴 증가하는 부분수열 문제랑 거의 같은데 그 수열을 출력해야 하기 때문에 조금 더 추가해야 할 부분들이 있다.

일단 전에 풀었던 코드에서 그냥 lis 배열을 출력시키면 이상한 값들이 나온다.

예를 들어 10 20 40 50 30 이 있을 때 lis배열이 10 20 40  50에서 10 20 30 50 으로 바뀌는데 이는 실제 증가하는 부분 수열이 되지 못하기 때문이다. 길이만 구할 수 있는 알고리즘이었기 때문에 lis배열을 그대로 출력하면 안된다.

그래서 ind라는 배열을 추가해서 ind[i]를 i번째 값이 lis배열에 추가된 인덱스로 정의한다.

예를 들어 10 20 40 30에서 ind[1]=1,ind[2]=2,ind[3]=3,ind[4]=3이 된다.

이렇게 하고 ind배열을 뒤에서부터 보면서 가장 긴 증가하는 부분 수열의 길이와 일치하면 해당 인덱스의 수가 부분 수열의 마지막 수가 될 것이다. ind[4]부터 볼 때 ind[4]는 3으로 가장 긴 증가하는 부분 수열의 길이와 같으니까 3이 부분 수열의 마지막이 되고, 그 다음으로 ind[3]은 3이니까 넘기고 ind[2]가 2니까 부분 수열의 마지막에서 2번째가 된다.

int check = ans;
    int cnt = 0;
    for(int i=N;i>=1;i--){
        if(ind[i]==check){
            lastarr[++cnt]=arr[i];
            check--;
        }
    }

이런 식으로 체크를 하면서 어떤 값들이 부분 수열에 들어가있는지 역순으로 판단할 수 있다.

#include<stdio.h>
int N,ans;
long long lis[1000004];
long long ind[1000004];
long long arr[1000004];
long long lastarr[1000004];
int pos(int s, int e, long long v)
{
    if(s==e) return s;
    int mid = (s+e)/2;
    if(lis[mid]<v){
        return pos(mid+1,e,v);
    }
    else{
        return pos(s,mid,v);
    }
}
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%lld",&arr[i]);
        if(ans==0){
            ans=1;
            lis[ans]=arr[i];
            ind[1]=1;
        }
        else{
            if(lis[ans]<arr[i]){
                ans++;
                lis[ans]=arr[i];
                ind[i]=ans;
            }
            else{
                int x = pos(1,ans,arr[i]);
                lis[x]=arr[i];
                ind[i]=x;
            }
        }
    }
    printf("%d\n",ans);
    int check = ans;
    int cnt = 0;
    for(int i=N;i>=1;i--){
        if(ind[i]==check){
            lastarr[++cnt]=arr[i];
            check--;
        }
    }
    for(int i=ans;i>=1;i--){
        printf("%lld ",lastarr[i]);
    }
}

전체 코드이다.