[C/C++] 백준 #1965 상자넣기(가장 긴 증가하는 부분수열)

이번 문제는 가장 긴 증가하는 부분수열을 찾는 문제입니다.

 

box in box

 

문제의 알고리즘 힌트에는 동적 프로그래밍을 이용하라고 되어 있지만, 동적 계획법을 이용하는 경우에는 $O(N^2)$ 알고리즘으로 풀어야 합니다.  그에 비해 약간의 정책을 이용해서 풀면 $O(N\log N)$ 알고리즘으로 풀 수 있습니다.

 

가장 긴 증가하는 부분수열이라는 것은, 부분수열중에 단순 증가하는 수열을 찾는 것입니다.

예를 들어서, 1 6 2 5 7 3 5 6 이란 수열이 있습니다.  부분수열은 순서를 지키면서, 이 수열에서 몇개의 수를 뽑아내는 것을 말합니다.  예를 들어서 1 6 2 5 도 이 수열의 부분수열이고, 1 2 7 6도 이 수열의 부분수열이 됩니다.  그런데, 증가하는 부분수열은 앞의 숫자보다 뒤의 숫자가 큰 경우를 의미합니다.  1 6 2 5는 부분수열이긴 하지만, 증가하는 부분수열은 아닙니다.  1 2 5 7 이라면, 증가하는 부분수열이 됩니다.  이렇게 증가하는 부분수열 중 가장 긴 증가하는 부분수열이 무엇인가를 찾는 것이 이번 문제입니다.

 

만약 가장 긴 증가하는 부분수열을 찾아서 출력하라고 한다면, 동적 계획법을 사용해서 풀어주는 것이 좋습니다.  하지만 단순 길이만 구하는 것이라면 다음과 같은 알고리즘을 적용할 수 있습니다.

 

1) 빈 배열 v를 하나 생성합니다.

2) 수열의 모든 수 s에 대해서

2-1) 배열 v가 비었거나, v의 마지막 원소가 s보다 작다면, s를 배열 v에 추가합니다.

2-2) 그렇지 않다면, 배열 v중 s보다 크거나 같은 최소의 수 대신에 s를 넣습니다.

3) 모든 수에 대해서 처리가 완료되면, 배열 v의 길이가 가장 긴 증가하는 부분수열의 길이입니다.

 

앞의 예제에서 들었던 1 6 2 5 7 3 5 6 을 예로 들어볼께요.

1) 빈 배열 v

2-1) v에 1 추가

1

2-1) v에 6 추가

1

6

2-2) v에서 2이상 수중 최소의 수인 6에 2를 넣음

1

2

2-1) v에 5 추가

1

2

5

2-1) v에 7 추가

1

2

5

7

2-2) v의 5의 자리에 3 넣음

1

2

3

7

2-2) v의 7의 자리에 5 넣음

1

2

3

5

2-1) v에 6 추가

1

2

3

5

6

 

그래서 이 수열의 답은 5입니다.  가장 긴 증가하는 부분수열은 1 2 3 5 6 이기도 하지만, 배열 v에 들어있는 것이 최종 값은 아닙니다.  배열 v는 단지 길이만을 구하기 위한 수단입니다.

 

이 알고리즘의 핵심은 배열 v는 항상 정렬된 상태를 유지한다는 것입니다.  그렇기때문에 s보다 크거나같은 값 중 최소값의 위치를 찾을때 이분탐색을 사용할 수 있습니다.  그래서 알고리즘 효율이 $O(N\log N)$이라고 할 수 있습니다.

 

이분탐색을 할 때, 저는 lower_bound 함수를 사용했습니다.  배열 v는 정렬된 상태이긴 하지만, s보다 크거나 같은 값 중에 최소값을 찾기 위해서는 lower_bound 함수가 좋습니다.  만약 s보다 큰 값 중 최소값을 찾는 조건이라면 upper_bound 함수를 사용하셔야 합니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1965
//        - by Aubrey Choi
//        - created at 2019-10-10
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

//    LIS
int main()
{
    int n, s, cur = 0;
    static int v[1000];
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d", &s);
        if(cur == 0 || v[cur - 1] < s) v[cur++] = s;
        else
        {
            int *p = std::lower_bound(v, v + cur, s);
            *p = s;
        }
    }
    printf("%d\n", cur);
    return 0;
}