백준 14002번. 가장 긴 증가하는 부분 수열 4(c++) / LIS

n의 크기가 크지 않아서 n^2으로 푸신 분들도 계시겠지만

글쓴이는 nlogn LIS 알고리즘을 사용하여 풀었습니다.

특히, 이 문제는 요소들을 구해야 하기 때문에 LIS 요소 역추적하는 부분도 구현했습니다.

 

 

블로그에 LIS 요소 역추적하는 방법에 대해서도 포스팅 했으니 참고바랍니다.

jungahshin.tistory.com/7

[Algorithm] LIS 요소 역추적하기(backtracing)

 

코드 첨부

// 가장 긴 증가하는 부분 수열 4
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<int> v;
vector<int> LIS;
vector<int> backtrace;
vector<int> ans;
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>m;
        v.push_back(m);
    }
 
    for(int i=0; i<v.size(); i++){
        if(LIS.empty() || LIS.back()<v[i]){
            LIS.push_back(v[i]);
            backtrace.push_back(LIS.size()-1);
        }else{
            int idx = lower_bound(LIS.begin(), LIS.end(), v[i])-LIS.begin();
            backtrace.push_back(idx);
            LIS[idx] = v[i];
        }
    }
 
    int temp = LIS.size()-1;
    for(int i=backtrace.size()-1; i>=0; i--){
        if(backtrace[i]==temp){
            temp--;
            ans.push_back(v[i]);
        }
    }
 
    sort(ans.begin(), ans.end());
 
    cout<<ans.size()<<"\n";
    for(int i=0; i<ans.size(); i++){
        if(i==ans.size()-1){
            cout<<ans[i]<<"\n";
        }else{
            cout<<ans[i]<<" ";
        }
    }
    
    return 0;
}

 

 

문제 첨부

www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4