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

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

문제 요약

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

사용 알고리즘

이분탐색

입출력

• 입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
• 출력: 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ``` 예제1

입력 6 10 20 10 30 20 50 출력 4

## 풀이
이 문제는 dp를 사용하는 문제가 아니다. 범위가 너무 넓기 때문에 시간초과가 나게 된다. 이분탐색을 이용하면 $O(N log N)$만에 풀 수 있다. 숫자를 차례대로 입력받을때마다 배열에 추가한다. 추가할때 지금까지의 수 중에서 제일 큰 수이면 가장 뒤에 추가하고 그렇지 않은 경우에는 그 수 이상인 수중에서 가장 작은 수를 대체한다. 길이만 구하면 되므로 그냥 덮어씌우는 방식으로 풀면 풀 수 있다. 

## 어려웠던 점
아이디어가 어려웠다.

## 배운 점 / 느낀 점
이분탐색 STL 함수에 대해서 더 잘 알게 되었다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> a;

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

    cin >> n;
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        auto it = lower_bound(a.begin(), a.end(), t);
        if(it == a.end()){
            a.push_back(t);
        }
        else{
            *it = t;
        }
    }
    cout << a.size();
    return 0;
}