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

#문제

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

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

 

#작성 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int serial[1000001];
vector<int> asc;
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>serial[i];
    }
    
    for(int i=1; i<=n; i++){
        if( asc.empty() ){
            asc.push_back(serial[i]);
            continue;
        }
        else{
            if( asc.back() < serial[i] ){
                asc.push_back(serial[i]);
                continue;
            }
            else{
                vector<int>::iterator iter = lower_bound(asc.begin(), asc.end(), serial[i]);
                *iter = serial[i];
                // asc에서 serial[i]보다 최초로 큰 원소를 찾고, serial[i]로 대체한다. 
                continue; 
            }
        }
    }
    cout<<asc.size()<<'\n';
    return 0;
}

##

이분탐색으로 어떻게 푸는 것이 좋을지 전혀 떠오르지 않아서

https://ferrante.tistory.com/54, https://mygumi.tistory.com/303?category=677288 참고하여 이분탐색으로 푸는 방법을 공부했다.

 

lower_bound 함수와 upper_bound 함수는 <algorithm> 헤더파일에 포함되어 있는 함수.

https://okayoki2484.tistory.com/135

BOJ 10816번 :: 숫자 카드 2