[C/C++] 백준 #2631 줄세우기(가장 긴 증가하는 부분수열)

이번 문제는 동적계획법을 이용해서 풀어도 되겠지만, 기본적으로 가장 긴 증가하는 부분수열(LIS; Longest Incremental Subsequence)의 풀이법을 이용하셔서 푸시는 것이 좋습니다.  일반적인 동적계획법으로 풀 경우에는 알고리즘 시간복잡도가 \(O(N^2)\)이지만, 가장 긴 증가하는 부분수열 풀이법을 이용하시면 \(O(N \log N)\) 시간복잡도로 풀 수 있습니다.

 

make a line

 

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

 

이 문제를 가장 긴 증가하는 부분수열 문제라는 것을 인지하는 것이 관건입니다.

문제에서 예로 든 3 7 5 2 6 1 4 를 생각해보죠.  문제에서는 위치를 옮기는 4개의 숫자에 대해서 이야기를 했는데요.  쉽게 접근할 수 있는 방법은 이미 순서가 올바른 수들은 남겨두고 나머지 수들만 옮기는 방법입니다.  예를 들어서 3 5 6 은 순서가 올바른 부분수열입니다.  이 올바른 부분수열을 제외한 나머지 숫자들을 적당한 곳에 끼어넣기하면 됩니다.  그러면 순서가 올바른 부분수열 중 가장 긴 것을 찾아야 최적의 해를 찾을 수 있을겁니다.  그래서 가장 긴 증가하는 부분수열 알고리즘을 이용하였습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2631 - Make a Line
//        - by Aubrey Choi
//        - created at 2020-01-21
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, stack[200], sp=1, s, i;
    scanf("%d%d",&n,stack);
    for(i=1;i<n;i++)
    {
        scanf("%d",&s);
        if(stack[sp-1]<s) stack[sp++]=s;
        else *std::lower_bound(stack,stack+sp,s)=s;
    }
    printf("%d\n",n-sp);
}