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

https://www.acmicpc.net/problem/12015

이진탐색의 사용은 무궁무진하구나...
처음엔 엥? 아무리봐도 dp문제인데? 했는데 시간복잡도가 O(N^2)이면 못푸는 문제더라...^^ 아무리봐도 모르겠어서 인터넷 보면서 풀었다..

풀이 과정

1. 결과 배열을 만들고 첫 번째 입력 배열 값을 넣는다.

2. 입력 배열을 돌며 현재 저장된 결과 배열의 마지막 값 보다 큰지 확인한다.

3. 만약 크면 뒤에 삽입, 그렇지 않으면 현재 원소보다 크거나 같은 첫 번째 결과 값과 바꾼다.

   {10,20,30,15,20,25} 가 존재한다고 했을 때
   i=0) result = {10}
   i=2) result = {10,20,30}
   i=3) restlt = {10,15,30}

   이유는 다른 부분배열로 대체하기 위해서이다.
   20을 15로 바꾼다고해서 길이가 달라지진 않는다.
   다만 다음에 20을 만나면 30위치에 20이 들어오고, 25를 만나면 길이가 증가하게 된다.
   즉, 15부터 reslt의 end까지 언제나 바뀔 준비를 하고있는 것이다.증가하는 부분 수열이므로 결국 작은 값부터 순차적으로 바뀌는 것 이니깐..

4. 끝까지 돌고 나서 길이를 출력한다.
   (result 배열 자체는 증가하는 부분 수열이 아닐 수도 있다. 3번의 이유로 바뀔 준비를 하다가 만 배열일 수도 있기 때문이다.그러나 길이는 동일하다.)

시간복잡도

3번에서 대체할 수를 찾는 방법으로 이진탐색을 쓰면 logN으로 금방 찾을 수 있다. n번을 탐색하니
$O(nlogn)$

구현

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

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

    int n;
    cin >> n;
    vector<int> seq(n + 1);
    vector<int> res;

    for(int i = 1; i <= n; i++){
        cin >> seq[i];
    }

    res.push_back(seq[1]);
    
    for(int i = 2; i <= n; i++){
        if(seq[i] > res.back()) {
            res.push_back(seq[i]);
        } else {
            auto it = lower_bound(res.begin(), res.end(), seq[i]);
            *it = seq[i];
        }
    }
    
    cout << res.size() << endl;
    
    return 0;
}