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

[문제]

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

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

[문제 풀이]

기존에 풀었던 가장 긴 증가하는 부분 수열에서 풀었던 방식을 이용해서 풀었다.

DP를 이용해서 부분 수열의 가장 긴 길이가 몇인지를 파악한 후에 뒤에서 부터 O(n)을 이용해서 순서대로 해당 길이에 맞은게 있으면 그 길이로부터 1씩을 제거하면서 파악하였다.

 

입력을 해주면서 동시에 각 수의 길이값을 파악하였다.(19~28)

해당 수의 길이가 몇인지를 파악하면서 벡터에 넣어주었다.(31~36)

벡터에 넣어진 값을 뒤에서부터 순서대로 출력한다.(31~36)

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> sequence(n+1);
 
    vector<int> increase;
    vector<int> DP(n+1);
 
    DP[0] = 1;
    int len = 0;
 
    for(int i = 1;i<=n;i++){
        cin>>sequence[i];
        DP[i] = 1;
        for(int j = 1;j<i;j++){
            if(DP[i]<=DP[j] and sequence[j]<sequence[i]){
                DP[i] = DP[j] + 1;
            }
        }
        len = max(len, DP[i]);
    }
 
    cout<<len<<endl;
    for(int i = n;i>0;i--){
        if(DP[i] == len){
            increase.push_back(sequence[i]);
            len--;
        }
    }
 
    int size = increase.size();
 
    for(int i = increase.size()-1;i>=0;i--){
        cout<<increase[i]<<" ";
    }
 
    return 0;
}