[C++][백준 14003] 가장 긴 증가하는 부분 수열 5

[문제]

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

[문제 풀이]

수열을 구하는 부분을 가장 긴 증가하는 부분 수열4 에서 했던 방식으로는 (N^2)이 이루어지므로 해당 문제의 조건인

N (1 ≤ N ≤ 1,000,000)

를 만족시키지 못한다.

고로, 가장 긴 증가하는 부분 수열2 에서 했던 방식으로 만들 경우 시간복잡도가(N log N)이니 해당 방식을 이용해서 수열을 구하는 것이 이번 문제의 키 포인트다.

 

하지만 lower bound를 이용하는것까지는 쉽게 유추가 되지만 해당 벡터의 사이즈만을 이용하기에는 오류가 나는 부분이 생길 것이라는 점을 쉽게 파악할 수가 있다.

그러므로 단순히 벡터의 size를 계속 저장해두는 방식이 아닌 벡터에 넣어둘때의 위치를 이용해서 현재 수열의 길이를 파악하도록 하자.

 

가장 긴 증가하는 부분 수열2 의 방식을 이용하지만 DP 벡터에 현재 숫자가 어느 위치에 가는지를 입력해주자. (14~27)

뒤에서부터 순서대로 수열의 길이 n부터 시작해서 1씩 뺀값의 수열을 벡터에 입력해주자.(34~42)

해당 벡터를 출력.(44~46)

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> augment;
    vector<int> sequence;
    vector<int> DP(n);
    for(int i = 0;i<n;i++){
        DP[i] = 1;
        int temp;
        cin>>temp;
        augment.push_back(temp);
        if(sequence.size() == 0 or sequence.back() < temp){
            sequence.push_back(temp);
            DP[i] = sequence.size();
        }
        else{
            *lower_bound(sequence.begin(),sequence.end(),temp) = temp;
            DP[i] = lower_bound(sequence.begin(),sequence.end(),temp) - sequence.begin() + 1;
        }
    }
    cout<<sequence.size()<<endl;
 
    int cnt = sequence.size();
 
    vector<int> answer;
 
    for(int i = n -1 ;i>=0;i--){
        if(cnt == 0){
            break;
        }
        if(DP[i] == cnt){
            answer.push_back(augment[i]);
            cnt--;
        }
    }
 
    for(int i = answer.size() - 1;i >= 0;i--){
        cout<<answer[i]<<" ";
    }
 
    cout<<endl;
    return 0;
}