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

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

 

정답코드

• C++의 lower_bound, upper_bound
  C++에서는 이진탐색으로 원소를 탐색하는 lower_bound, upper_bound 메서드를 제공한다.
  lower_bound : 찾으려는 key 값보다 같거나 큰 숫자가 등장하는 인덱스를 반환한다.
  upper_bound : 찾으려는 key 값을 초과하는 숫자가가 등장하는 인덱스를 반환한다.

int arr[]={0,1,2,3,4,5,5,5,6,7};
lower_bound(arr.begin(), arr.end(), 5) - arr.begin();
// 5 반환

upper_bound(arr.begin(), arr.end(), 5) - arr.begin();
// 8 반환

 

 

초기 상태

10, 30이 vector(stack)에 들어가 있는 상태에서 seq.back()이  20보다 작으므로 seq.lower_bound(20)으로 20보다 크거나 같은 값이 있는 인덱스를 찾는다.

 

인덱스 위치에 새로 들어온 값(20)으로 변경한다.

 

 

같은 방식으로 40과 25를 비교하여 seq를 구한다. 

 

30과 50을 같은 방식으로 seq vector에 삽입하면 다음과 같은 가장 긴 증가하는 부분 수열만 남게된다.

 

 

만약 다음에 23이 삽입된다면

seq는 다음과 같다!

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 1'000'000
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
int N;
vector<int> seq;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;

    seq.push_back(MAX);
    fse(0,N,1){
        int arr;
        cin>>arr;
        if(seq.back() < arr){
            seq.push_back(arr);
        }else{
            int idx=lower_bound(seq.begin(),seq.end(),arr)-seq.begin();
            seq[idx]=arr;
        }
    }

    cout<<seq.size();
}