[Baekjoon,12015] 가장 긴 증가하는 부분 수열 2

DP로는 안된다.

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 이 문제는 수열의 길이가 최대 1,000,000 이므로 백준 11053번 문제의 해결 방법이었던 DP로는 해결할 수 없다.

// 이 방식은 사용할 수 없다. 
int len, seq[MAX], cache[MAX];
int LIS(int start)
{
    int& ret=cache[start+1];
    if(ret!=-1)
        return ret;
    ret=1;
    for(int next=start+1;next<len;++next)
        if(start==-1 || seq[start]<seq[next])
            ret=max(ret,LIS(next)+1);
    return ret;
}
int main(void)
{
    cin>>len;
    for(int i=0;i<len;++i)
    {
        cin>>seq[i];
        cache[i]=-1;
    }
    cache[len]=-1;
    cout<<LIS(-1)-1;
    return 0;
}

하나씩 추가하며 이분 탐색하자

해결 방법은 다음과 같은 방법으로 이분 탐색을 활용하는 것이다. 먼저 주어진 값들을 하나씩 수열에 추가하며 이 값이 수열의 제일 큰 값보다 크면 수열에 추가한다. 그리고 개수를 카운트한다. 만약 비교했을 때 주어진 값이 수열의 제일 큰 값보다 작다면 수열에서 같거나 큰 제일 왼쪽 값, 즉 lower_bound()를 이용하여 찾은 값을 주어진 값으로 바꾼다. 이때는 개수를 카운트 하지 않는다.

이렇게 하면 수열은 계속해서 정렬되어 있는 상태이며 중간에 삽입되어야 하는 값들이 나오면 lower_bound()를 이용하여 삽입한다. 삽입해야 할 때는 수열의 최대 값 보다 작은 값이 주어진 경우이다. 수열은 LIS가 아니지만 길이는 LIS의 길이가 맞다.

구현

구현 시 음의 무한대 값을 수열에 추가하고 시작하는 것을 볼 수 있다.

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

const int NEG_INF=-987654321;

int main()
{
    int len, ret=0;;
    cin>>len;
    
    vector<int> perm;
    perm.push_back(NEG_INF);
    
    for(int i=0;i<len;++i)
    {
        int n;
        scanf("%d",&n);
        if(perm.back()<n)
        {
            perm.push_back(n);
            ++ret;
        }
        else
        {
            vector<int>::iterator it=lower_bound(perm.begin(), perm.end(), n);
            *it=n;
        }
    }
    cout<<ret<<endl;
    return 0;
}