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

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

 

www.acmicpc.net

풀이

LIS 알고리즘 문제이다. 일반적으로 LIS 문제는 동적계획법으로 풀 수 있는 전형적인 문제이지만, 이 문제에서는 N의 최댓값이 1,000,000이므로 다른 방법으로 해결해야한다. 아래의 코드는 이진 탐색을 이용한 LIS 알고리즘이다. C++ STL에 구현되어있는 lower_bound()를 이용해서 해결했다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int a[1000001];
vector<int> lis;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    lis.push_back(-1);
    for (int i = 0; i < n; i++) {
        if (lis.back() < a[i]) lis.push_back(a[i]);
        else {
            auto it = lower_bound(lis.begin(), lis.end(), a[i]);
            *it = a[i];
        }
    }
    cout << lis.size() - 1 << '\n';
    return 0;
}