[14002] 가장 긴 증가하는 부분 수열 4

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

14002 - 가장 긴 증가하는 부분 수열 4

본문

수열 $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 1000$)이 주어진다.

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

출력

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

제한

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

---

풀이

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

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

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 19

#include <stdio.h>

typedef struct Node {
    int v;
    int idx;
} ND;

#define MAX_IDX 1001
const int START = 0;
const int END = -1;

int arr[MAX_IDX];

ND LIS[MAX_IDX];
int lis[MAX_IDX];
int pre[MAX_IDX];
int lis_len;
int lis_cur;
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].v < x) {
            s = mid + 1;
        } else {
            e = mid;
        }
    }

    return e;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    lis_len = START;
    lis_cur = START;
    LIS[START] = (ND){arr[START], START};
    pre[START] = END;

    for (int i = 1; i < n; ++i) {
        int x = arr[i];

        if (x > LIS[lis_len].v) {
            pre[i] = LIS[lis_len].idx;
            LIS[++lis_len] = (ND){x, i};
            lis_cur = i;
        } else {
            int t = lower_bound(x);
            if (t > 0) {
                pre[i] = LIS[t - 1].idx;
            } else {
                pre[i] = END;
            }
            LIS[t] = (ND){x, i};
        }
    }

    printf("%d\n", lis_len + 1);
    for (int i = 0; lis_cur > END; ++i) {
        lis[i] = arr[lis_cur];
        lis_cur = pre[lis_cur];
    }

    for (int i = lis_len; i >= 0; --i) {
        printf("%d ", lis[i]);
    }
    return 0;
}