DP + LIS (BOJ 14002)

문제

가장 긴 증가하는 부분 수열 4

알고리즘

1. 각 인덱스까지 이어지는 수열의 최장길이(LIS)를 저장하는 DP를 생성
2. LIS를 기준으로 DP를 역추적해 수열(stack)을 생성
   

#include <bits/stdc++.h>

using namespace std;

int N, lis = 0;
vector<int> arr;
stack<int> ans;
int DP[1000] = {0, };

void input(){
    cin >> N;

    for(int i=0; i<N; i++){
        int num;
        cin >> num;

        arr.push_back(num);
    }

    DP[0] = 1;
} 

void makeDP(){
    for(int i=1; i<N; i++){
        int now = arr.at(i);

        for(int j=0; j<i; j++){
            if(arr.at(j) < now){
                DP[i] = max(DP[i], DP[j]+1);
                lis = max(DP[i], lis);
            }
        }
    }
} // index까지 가장 긴 수열의 길이(LIS)를 DP에 저장

void printDP(){
    for(int i=0; i<N; i++){
        cout << DP[i] << " ";
    }
    cout << endl;
}

void buildAns(){
    for(int i=N-1; i >= 0; i--){
        if(DP[i] == lis){
            ans.push(arr.at(i));
            lis--;
        }
    }
} // lis를 기준으로 DP 역추적


void printAns(){
    if(ans.size() == 0)
        ans.push(arr.at(0));

    cout << ans.size() << endl;

    while(!ans.empty()){
        cout << ans.top() << ' ';
        ans.pop();
    }
    cout <<endl;
}

void run(){
    input();
    makeDP();
    buildAns();
    printAns();
}


int main(){
    run();
    return 0;
}