풀이
LIS를 구해주자!
주어진 두 축을 주어진 선으로 연결했을 때 겹치는 선이 없어야 한다!
한 축 x를 기준으로 잡아 pair를 정렬해주자.
이제 정렬한 축 x를 기준으로 한바퀴 쭉 돌면서
순서대로 마주치는 y축에 대해서 LIS를 수행해주자!
코드
#include <stdio.h>
#include <algorithm>
#define fst first
#define snd second
using namespace std;
int n, len, lis[100];
pair<int, int> a[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &a[i].fst, &a[i].snd);
sort(a, a + n);
for (int i = 0; i < n; i++) {
auto it = std::lower_bound(lis, lis + len, a[i].snd);
if (!(*it)) len++;
*it = a[i].snd;
}
printf("%d", n - len);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge