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

풀이 요약

LIS 응용 문제. $N$ 최대 범위가 1e6 이므로 기존 DP 방식은 $O^2$ 라 시간초과가 날 것이다. LIS 의 최대를 물어보는 거라면, 이분탐색을 통해 더 빠르게 구할 수 있다.

풀이 상세

1. 이분 탐색을 통해 다음과 과정을 거쳐 LIS 를 구할 수 있다.

   • 처음에 일단 dp 리스트에 arr[0] 을 넣어주자.

   • 그 다음 arr[i] 값 부터 현재 dp 에 있는 최댓값보다 크다면 그냥 넣어주고, 최댓값보다 작다면 더 작은 수가 있는지 이분 탐색을 통해 찾아 해당 인덱스 덮어 쓰면 된다.

   • 예제를 통해 코드를 실행하면 dp[10] → dp[10,20] → dp[10,20] → dp[10,20,30] → dp[10,20,30] → dp[10,20,30,50] 과정이 진행될 것이다.

정답

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int N, arr[1000005];
vector<int> res;

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
}

void solve() {
    res.push_back(arr[1]);
    for (int i = 2; i <= N; i++) {
        if (res.back() < arr[i])
            res.push_back(arr[i]);
        else
            res[lower_bound(res.begin(), res.end(), arr[i]) - res.begin()] =
                arr[i];
    }
}

void output() { cout << res.size(); }

int main() {
    input();
    solve();
    output();
    return 0;
}