[백준(BOJ)] 12015번 : 가장 긴 증가하는 부분 수열 C++ 풀이 (이분 탐색)

접근:

접근은 처음에는 DP로 하려다가 너무 길 것 같아서 포기하였고,

아이디어가 떠오르지 않아서 검색을 해보았다.

그랬더니, 이분 탐색을 이용한 풀이가 있었다.

 

 

전략:

가장 긴 수열을 만들기 위해서는 그 숫자들의 간격이 가장 작게 숫자를 설정하는 것인데,

하나 씩 조사를 할 때, 해당하는 값을 포함하는 새로운 수열을 만드는 것처럼

배열 내의 값을 inplace 하여 계속 해서 업데이트 해나가는 방식이다.

(작동 방식은 그러한데 직접 해보기 전에는 이해하기 어려웠다.)

매 값을 입력 받을 때,  수열 맨 뒤의 값이 더 작으면 뒤로 삽입 해주고 작다면, 배열 내에 그 값보다 크면서 제일 작은 것을 찾아서 이 값으로 바꾼다.

 

코드:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for(int i=0;i<n;i++){
        int temp;
        cin >> temp;
        if(v.empty() || v.back() < temp){
            v.push_back(temp);
        }else{
            *lower_bound(v.begin(), v.end(), temp) = temp;
        }
    }

    cout << v.size() <<'\n';
    return 0;
}