백준 14003번 가장 긴 증가하는 부분 수열 5 / LIS

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

 

이건 유사문제

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

 

 

그냥 LIS 계산하고 LIS의 길이만 묻는게 아니라 LIS 원본을 묻는 문제

index 배열을 만들고 해당 배열에 i는 LIS의 몇번 index에 들어갔는가를 저장함

마지막에 뒤에서부터 --하면서 같은 숫자면 넣고 reverse

#include <bits/stdc++.h>
using namespace std;

#define INF 2147483647

int main()
{
    int N;
    cin >> N;

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

    vector<int> lis_vec;
    lis_vec.push_back(-INF);
    for (int i = 0; i < N; i++) {
        if (lis_vec.back() < input[i]) {
            lis_vec.push_back(input[i]);
            index[i] = lis_vec.size() - 1;
        }
        else {
            auto itr = lower_bound(lis_vec.begin(), lis_vec.end(), input[i]);
            *itr = input[i];
            index[i] = itr - lis_vec.begin();
        }
    }
    
    int lis = lis_vec.size() - 1;
    cout << lis << '\n';

    vector<int> answer;
    for (int i = N - 1; i >= 0; i--) {
        if (index[i] == lis) {
            answer.push_back(input[i]);
            lis--;
        }
    }

    for (auto ritr = answer.rbegin(); ritr != answer.rend(); ritr++) {
        cout << *ritr << ' ';
    }
    
    return 0;
}