[12015] 가장 긴 증가하는 부분 수열 2

문제 링크 : https://www.acmicpc.net/problem/12015

12015 - 가장 긴 증가하는 부분 수열 2

본문

수열 $A$가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 $A = \lbrace 10, 20, 10, 30, 20, 50 \rbrace$ 인 경우에 가장 긴 증가하는 부분 수열은 $A = \lbrace $ 10, 20, 10, 30, 20, 50 $\rbrace$ 이고, 길이는 4이다.

입력

첫째 줄에 수열 $A$의 크기 $N$ ($1 \leq N \leq 1000000$)이 주어진다.

둘째 줄에는 수열 $A$를 이루고 있는 $A_i$가 주어진다. ($1 \leq A_i \leq 1000000$)

출력

첫째 줄에 수열 $A$의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

제한

시간 제한	메모리 제한
1sec	512MB

---

풀이

LIS 기본 문제이다. 풀이는 참고로 대체.

• 참고 알고리즘 : LIS ( O(nlogn) )

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 16

#include <stdio.h>

#define MAX_IDX 1000000

int LIS[MAX_IDX];
int lis_len;
int n;

int lower_bound(int x) {
    int s = 0, e = lis_len + 1;
    int mid;

    while (s < e) {
        mid = (s + e) / 2;

        if (LIS[mid] < x) {
            s = mid + 1;
        } else {
            e = mid;
        }
    }

    return e;
}

int main() {
    scanf("%d %d", &n, &LIS[0]);
    lis_len = 0;

    for (int i = 1; i < n; ++i) {
        int a;
        scanf("%d", &a);

        if (a > LIS[lis_len]) {
            LIS[++lis_len] = a;
        } else {
            LIS[lower_bound(a)] = a;
        }
    }

    printf("%d", lis_len + 1);
    return 0;
}