백준 1365 꼬인 전깃줄 C++

간단한 해설?

문제 양치기를 너무 많이해서 그런가 문제만 봐도 그냥 단순한 LIS임이 명백했다.(전깃줄 문제랑 비슷해보임)

lower_bound를 통해 이분탐색으로 풀었다.

답

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,a;
    cin>>n;
    deque<int> v;
    cin>>a;
    v.push_back(a);
    int ans=0;
    for(int i=1;i<n;++i){
        cin>>a;
        auto it=lower_bound(v.begin(),v.end(),a);
        if(it==v.end()){
            v.push_back(a);
        }
        else{
            ++ans;
            v[it-v.begin()]=a;
        }
    }
    cout<<ans;
}