[DP/LIS] 11053 가장 긴 증가하는 부분 수열

예전에 풀었던 문제인데 O(n2)방식이 아닌 O(NLOGN)방식으로 다시 풀어봤다.

벡터에는 최장 길이 부분 수열이 만들어 진다.

값이 들어있는 배열을 처음부터 끝까지 반복해 가면서 현재 인덱스의 원소가 벡터안에 어느 위치에 들어가야 하는지를 찾아서 그곳에 값을 넣어주는 방식이다.

자세한 내용은 아래 링크에 있으니 먼저 문서를 보고 나서 코드를 보면 이해가 갈것이다.

클릭

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> vt;
vector<int>::iterator it;
int arr[1000];
 
 
vector<int>::iterator find(int x){
    
    for(it=vt.begin(); it<vt.end(); it++){
        if(x <= *it) break;
    }
    return it;
}
 
int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>arr[i];
    
    vt.push_back(arr[0]);
    for(int i=1; i<n; i++)
    {
        if(arr[i] > vt.back())
            vt.push_back(arr[i]);
        else{
            *find(arr[i]) = arr[i];
        }
    }
    
    cout<<vt.size()<<endl;
    
    return 0;
}