[개쉬운 풀이] 백준 14002 가장 긴 증가하는 부분 수열 4 (3일차)

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

 

문제

 

생각

1. 기본적인 LIS 문제이다. 이를 dp를 활용하여 해결해야한다.

2. 길이만 출력하는 것이 아닌 수열을 출력해야 하므로 vector를 이용하여서 같이 저장 및 업데이트 한다.

 

풀이

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1001;

int N;
vector<int> v;
int dp[MAX];
vector<int> LIS[MAX];
vector<int> answer;

void input(){
    cin >> N;
    v = vector<int> (N);
    for(int i = 0; i < N; i++){
        cin >> v[i];
    }
}

void sol(){
    for(int i = 0; i < N; i++){
        dp[i] = 1; //초기값
        LIS[i].push_back(v[i]);
        for(int j = 0; j < i; j++){
            if(v[i] > v[j]){
                if(dp[i] < dp[j] + 1){ //길이 비교
                    LIS[i].clear();
                    LIS[i] = LIS[j];
                    LIS[i].push_back(v[i]);
                    dp[i] = dp[j] + 1;
                }
            }
        }
        //최장 수열 판별
        if(answer.size() < LIS[i].size()){
            answer = LIS[i];
        }
    }
}

int main(){
    input();
    sol();
    cout << answer.size() << endl;
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    return 0;
}