Mini
[틀림] 백준 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;
}
'Algorithm > 이분탐색' 카테고리의 다른 글
[틀림] 백준 LIS 5 // 원복 LIS (0) | 2025.03.12 |
---|---|
프로그래머스 숫자게임 c++ // 이진탐색, 투포인터 (1) | 2024.10.27 |
[Algo] 백준 가장 긴 바이토닉 부분 수열 c++ // LIS, LDS, (dp), 이분탐색 (0) | 2024.09.15 |
리트코드 153 회전 정렬 배열에서 최소값 찾기 c++ // 이분탐색 (0) | 2024.05.30 |
백준 14003 LIS 5 c++ // LIS 이분탐색 오류수정, LIS 출력하는법 (0) | 2024.05.15 |