백준 14002 / 가장 긴 증가하는 부분 수열 4

LIS 문제

이번엔 길이만 출력하는 것이 아니라 수열 그 자체를 출력해야하는 문제다.

넘나 어려웠다.

https://naivep.tistory.com/9

여기서

배열을 하나 더 만들어, d의 값이 어느 인덱스의 값 때문에 변하는지 적어놓는 것이다.

그 후 완성된 수열의 가장 끝에 위치할 성분부터 v[i]에 적힌 인덱스 값으로 이동하여

벡터 안에 집어넣는다.

그 후 벡터를 sort한 후 출력하면 끝.

코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
 
 
 
int n;
int arr[1001];
int d[1001];
int v[1001];
vector<int>answer;
 
void go(int index) {
    if (index == -1) {
 
        return;
    }
    answer.push_back(arr[index]);
    go(v[index]);
 
}
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        v[i] = -1;
        d[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                v[i] = j;
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        ans = max(ans, d[i]);
    }
 
    cout << ans << endl;
 
    for (int i = 0; i < n; i++) {
        if (d[i]==ans){
            answer.push_back(arr[i]);
            go(v[i]);
            break;
        }
    }
 
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << " ";
    }
 
}