✅ 이분탐색 ✅ lower_bound

문제

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

풀이

dp로 풀면 시간 복잡도가 n제곱이 나오는데 이 문제는 n의 최댓값이 1,000,000이므로 n제곱으로 풀면 시간초과가 난다.
👉 이분탐색

dp를 통해 가장 긴 증가하는 부분 수열을 푸는 문제도 있으니 풀어보도록 하자.
[boj] (s2) 11053 가장 긴 증가하는 부분 수열

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, ans=1;
int arr[1000001];
vector<int> permutation;

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

    cin >> N;

    for(int i=0;i<N;i++){
        cin >> arr[i];
    }

    permutation.push_back(arr[0]);
    for(int i=1;i<N;i++){
        if(arr[i] > permutation.back()){
            permutation.push_back(arr[i]);
        }
        else{
            // arr[i] 보다 크나 같은 값이 처음으로 나타나는 위치에 넣음 (대치)
            int idx = lower_bound(permutation.begin(), permutation.end(), arr[i]) - permutation.begin();
            permutation[idx] = arr[i];
        }
    }

    cout << permutation.size() << "\n";
    
    return 0;
}