문제

문제 분석

가장 긴 증가하는 부분 수열의 길이는 기본적인 LIS 알고리즘으로 찾을 수 있다.
그러나 이 문제는 실제 수열을 출력하는 것이 관건이다.

각 원소가 LIS에 몇번에 속하는 지 기록한다.
이후 reverse로 돌면서 LIS의 N번째 원소부터 1번째 원소까지 출력하면 된다.

알고리즘

LIS

자료구조

vector

결과

• 성공

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

const int MAX_N = 1000000;
int N;

vector<int> seq;
vector<int> bucket;
vector<vector<int>> sourceIdxOfBucket(MAX_N);

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N;
    seq.resize(N);
    for ( int i = 0; i < N; i++ ){
        int a;
        cin >> a;
        seq[i] = a;
    }

    bucket.push_back(seq[0]);
    sourceIdxOfBucket[0].push_back(0);
    for ( int i = 0; i < N; i++ ){
        if ( bucket[bucket.size()-1] < seq[i] ){
            bucket.push_back(seq[i]);
            sourceIdxOfBucket[bucket.size()-1].push_back(i);
        }
        else {
            int idx = lower_bound( bucket.begin(), bucket.end(), seq[i] ) - bucket.begin();
            bucket[idx] = seq[i];
            sourceIdxOfBucket[idx].push_back(i);
        }
    }

    cout << bucket.size() << endl;
    int min = sourceIdxOfBucket[bucket.size()-1].back();
    for ( int i = bucket.size()-2; i >= 0; i-- ){
        //printf( "i : %d, min: %d\n", i, min );
        if ( sourceIdxOfBucket[i].back() > min ){
            vector<int>& sources = sourceIdxOfBucket[i];
            int idx = lower_bound(sources.begin(), sources.end(), min ) - sources.begin()-1;
            // printf( "idx %d\n", sources[idx]);
            bucket[i] = seq[sources[idx]];
            min = sources[idx];
        }
        else {
            min = sourceIdxOfBucket[i].back();
        }
    }

    for( size_t i = 0; i < bucket.size(); i++ ){
        cout << bucket[i] << " ";
    }

    return 0;
}

Other

lower_bound, upper_bound가 내놓는 값이 무엇인지 제대로 이해하자.

lower_bound는 trg value보다 작은 영역 [l, r) 에서 r 값을 return 한다.
upper_bound는 trg value보다 큰 영역 [l,r) 에서 l을 return 한다.