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

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

가장 긴 증가하는 부분 수열의5번째 문제입니다. LIS의 길이와 그 수열을 직접 출력해야 합니다.

 

N이 100만이므로 lower_bound를 이용하여 O(NlogN)의 시간이 걸리는 방법으로 LIS의 길이를 먼저 구합니다.

 

lower_bound를 이용하여 구한 dp배열원소는 실제 수열이 아니므로 실제 수열을 구하기 위해서

 

pair배열을 하나 둔다음 각각 반복문을 돌때마다 dp배열에서 해당하는 동작을 하는 ind와 그 값을 저장해 줍니다.

 

이후 pair 배열을 끝에서 부터 역추적하면서 수열을 찾아주면 됩니다. 예를 들어 수열의 길이가 4라면

 

pair배열의 끝에서부터 확인하며 ind가 3인값이 처음나오면 그 값이 LIS수열의 마지막 원소가 됩니다. 스택에 집어넣고 ind값을 1줄이고 다시 돌면서 ind가 2인값이 처음나올때를 push하면서 끝까지 돌면 LIS수열을 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <stack>

using namespace std;

int arr[1000001];
int ind = 0;
int dp[1000001];
pair<int,int> p[1000001];

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    stack<int> ans;
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
        if(i == 0) {
            dp[ind] = arr[i];
            p[i] = make_pair(ind, arr[i]);
        }
        else if(dp[ind] < arr[i]) {
            dp[++ind] = arr[i];
            p[i] = make_pair(ind, arr[i]);
        }
        else {
            int it = lower_bound(dp, dp+ind, arr[i]) - dp;
            dp[it] = arr[i];

            p[i] = make_pair(it, arr[i]);
        }
    }
    cout<<ind+1<<'\n';

    int cp = ind;
    for(int i = N-1; i >= 0; i--) {
        if(p[i].first == cp) {
            ans.push(p[i].second);
            cp--;
        }
    }

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