[PS] 백준 14003번: 가장 긴 증가하는 부분 수열 5

|

문제

내가 이해한 문제 내용

수열이 주어질 때 LIS의 길이와 해당 부분수열을 출력하라.

접근 방식

기존 LIS를 $O(N^2)$ DP로 해결했었고 더 개선한 것이 lower_bound()를 이용한 $O(NlgN)$ 풀이였는데 이 풀이를 까먹어서 좀 고생을 했다. 수열을 출력하는 부분이 핵심인데 lower_bound()로 숫자가 LIS 배열에 어떤 인덱스에 위치할지를 저장하여서 해결할 수 있었다.

어려웠던 점 & 배운 점

수열을 출력하는 부분이 너무 어려워서 꽤나 고생을 했고 다음과 같은 것들을 배웠다.

  • 삼항연산자는 리턴타입이 같아야 한다.
  • 반복자(iterator)를 이용해서 인덱스를 구하는 방법은 반복자 변수가 it이고 해당 벡터가 lis라고 할 때 it-lis.begin()으로 구할 수 있다.

시간복잡도

$O(NlgN)$

코드

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

int n,ans,max_index;
int index[1000000];
vector<int> a,lis;
vector<int>::iterator it;


int main(void)
{
    scanf("%d",&n);
    a.resize(n);
    for(int i=0; i<n; i++) scanf("%d",&a[i]);

    lis.push_back(a[0]);
    index[0] = 0;
    for(int i=1; i<n; i++){
        it = lower_bound(lis.begin(),lis.end(),a[i]);
        if(it==lis.end()) {
            lis.push_back(a[i]);
            index[i] = lis.size()-1;
        }
        else {
            index[i] = it-lis.begin();
            *it = a[i];
        }
        if(max_index < index[i]){
            max_index = index[i];
            ans = i;
        }
    }

    vector<int> real_lis;
    for(int i=ans,k=max_index; i>=0; i--){
        if(index[i]==k && a[i]<=a[ans]){
            real_lis.push_back(a[i]);
            k--;
        }
    }

    printf("%d\n",real_lis.size());
    for(int i=real_lis.size()-1; i>=0; i--) 
        printf("%d ",real_lis[i]);
    return 0;
}