백준2565 전깃줄

작성일 | In

문제 링크

  • http://icpc.me/2565

문제 출처

  • 2007 지역 본선 초등4

사용 알고리즘

  • LIS

시간복잡도

  • O(n log n)

풀이

문제에서는 전선을 교차하지 않게 하기 위애 제거해야 하는 개수를 물어보고 있습니다. 그러나 제거하는 관점에서 보며 문제를 해결하면 풀기 어려워집니다.
제거해야 하는 개수를 구하는 대신, 전선이 교차하지 않으면서 최대 몇 개까지 전선을 추가할 수 있는지를 구해도 문제는 풀리게 됩니다.
교차하지 않는 최대 개수는 LIS의 길이와 동일합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;

typedef pair<int, int> p;

int n, len, lis[100];
p 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 = lower_bound(lis, lis + len, a[i].snd);
		if (!(*it)) len++;
		*it = a[i].snd;
	}

	printf("%d", n - len);

	return 0;
}