2565 : 전깃줄

풀이

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

wookje.kwon's profile image

wookje.kwon

2017-08-16 23:52

Read more posts by this author