[Algorithm] 12015: 가장 긴 증가하는 부분 수열 2

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

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-19
문제 확인하기

풀이

• 해당 수열의 크기가 1,000,000 이 최대이기 때문에 의 방법으로는 풀 수 없다.
• 때문에 이분 탐색을 통해 의 방식으로 풀이한다.

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;
 
int N;
int arr[1000001];
vector<int> vec;
 
void Input(){
    cin >> N;
    
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
}
 
int binary_search(int target){
    int start = -1;
    int end = vec.size()-1;
    while(end > start+1){
        int mid = (start + end)/2;
        if(vec[mid] >= target){
            end = mid;
        }
        else start = mid;
    }
    return end;
}
 
void Solution(){
    vec.push_back(arr[0]);
    for(int i=1; i<N; i++){
        if(vec.back() < arr[i]){
            vec.push_back(arr[i]);
        }
        else {
            int idx = binary_search(arr[i]);
            vec[idx] = arr[i];   
        }
    }
    cout << vec.size() << endl;
 
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}