[틀림] 백준 2565 전깃줄 // 조합연속합, 이게 왜 LIS

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

* 풀이

• 완탐?
  • 조합으로 뽑아서 되는지 검사하면?
  • 조합연속합 공식 (완탐)
    • 100C1 + 100C2 + ... + 100C100 = 2^100 -1 -> 불가
• 혹시 LIS?

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n;
int lis[104],len;
vector<pair<int,int>> v;

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

   cin>>n;
   for(int i=0;i<n;++i) {
      int a,b;
      cin>>a>>b;
      v.push_back({a,b});
   }
   sort(v.begin(),v.end());

   for(int i=0;i<n;++i) {
      int idx = lower_bound(lis,lis+len,v[i].second)-lis;
      if(idx==len) {
         len++;
      }
      lis[idx]=v[i].second;
   }

   cout<<n-len;
}