가장 긴 증가하는 부분 수열 3

작성일 | In

[백준] 12738번 - 가장 긴 증가하는 부분 수열 3

문제 링크

12015번 문제와 거의 동일하나, 수열의 크기가 커서 동적 계획법의 시간복잡도 O(n2)으로는 해결할 수 없는 문제이다.
따라서 O(nlogn) 시간복잡도를 갖는 이분 탐색을 이용한 방법을 사용하여 문제를 풀었다.
LIS 이분 탐색 방법에 대한 자세한 내용은 아래 포스트를 참고하길 바란다.
[Algorithm] 최장 증가 부분 수열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

vector<int> longest;
int seq[1000001];
int n;

int main(void) {
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d", &seq[i]);

    longest.push_back(-10000000001);
    for(int i=1; i<=n; ++i) {
        if(longest.back() < seq[i])
            longest.push_back(seq[i]);
        else if(longest.back() > seq[i])
            *lower_bound(longest.begin(), longest.end(), seq[i]) = seq[i];
    }

    printf("%d", longest.size() - 1);
}
0%