[Baekjoon,14003] 가장 긴 증가하는 부분 수열 5

DP로 해결하기에는 너무 느리다. 따라서 이분 탐색을 활용한 방법(Baekjoon,12015 가장 긴 증가하는 부분 수열 2)으로 해결해야 한다. 하지만 문제는 $LIS$의 길이 말고도 실제 $LIS$를 출력해야 한다. 이에 대한 해결 방법은 직접 과정을 따라가다 보면 알 수 있다.

아래와 같은 예제를 이분 탐색으로 구하는 과정을 따라가 보자.

// input
6
10 20 8 30 20 50 

// output
4
10 20 30 50 

먼저 숫자 10이 $tmp$에 추가 될 것이며 이 수가 수열에 어느 인덱스에 추가 되었는지 표시하면 아래와 같다.

seq: 10 20  8 30 20 50 
pos:  0
tmp: 10

이 다음 20을 진행하면 10보다 크기 때문에 $tmp$뒤에 추가하여 아래처럼 될 것이다.

seq: 10 20  8 30 20 50 
pos:  0  1
tmp: 10 20 

다음 수인 8은 $tmp.back()$보다 작으므로 $lower bound$로 위치를 찾으면 10이 있는 위치에 들어가게 된다.

seq: 10 20  8 30 20 50 
pos:  0  1  0
tmp:  8 20 

설명은 여기서 생략하고 진행하는 과정만 보이겠다.

seq: 10 20  8 30 20 50 
pos:  0  1  0  2
tmp:  8 20 30

seq: 10 20  8 30 20 50 
pos:  0  1  0  2  1
tmp:  8 20 30

seq: 10 20  8 30 20 50 
pos:  0  1  0  2  1  3
tmp:  8 20 30 50

$tmp$는 당연히 $LIS$가 아니며 길이는 $LIS$의 길이와 같다. 여기서 눈치 챈 사람이 있겠지만 $pos$의 뒷 부분부터 앞으로 진행해 보면 $LIS$를 만들 수 있다는 것을 알 수 있다. 숫자 50 30 20 10 순서로 $pos$값을 확인해보면 $LIS$가 만들어 진 것을 볼 수 있다. 이것이 가능한 이유는 오른쪽으로 갈 수록 같은 $pos$일때 더 작은 값으로 갱신해 왔기 때문이다.

이를 구현하는 과정은 다음과 같다. $LIS$의 길이에서 1을 뺀 값인 3부터 $idx$를 시작하여 이와 일치하는 $pos$가 나오면 $idx$를 1 감소하고 해당 수를 스택에 넣는다. 이를 반복하고 나서 스택에 있는 수를 차례로 빼내면 $LIS$가 완성된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int MAX=1000001;

int N;
int seq[MAX], pos[MAX];

// 이분 탐색으로 LIS를 형성
int getLisLen()
{
    vector<int> lis;
    lis.push_back(seq[0]);
    for(int i=1;i<N;++i)
    {
        int cand=seq[i];
        if(lis.back()<cand)
        {
            lis.push_back(cand);
            // 현재 수가 추가된 위치를 넣는다. 
            pos[i]=lis.size()-1;
        }
        else
        {
            vector<int>::iterator it=lower_bound(lis.begin(),lis.end(),cand);
            *it=cand;
            // 현재 수가 추가된 위치를 넣는다. 
            pos[i]=int(it-lis.begin());
        }
    }
    return lis.size();
}

void printLis()
{
    int len=getLisLen();
    cout<<len<<endl;
    
    stack<int> st;
    int idx=len-1;
    // 뒤에서 부터 차례로 탐색한다.
    for(int i=N-1;i>=0;--i)
        if(pos[i]==idx)
        {
            st.push(seq[i]);
            --idx;
        }
    
    while(!st.empty())
    {
        cout<<st.top()<<' ';
        st.pop();
    }
}

int main()
{
    cin>>N;
    for(int i=0;i<N;++i)
        scanf("%d",&seq[i]);
    
    printLis();
    
    return 0;
}