백준 2565. 전깃줄

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

2565번: 전깃줄

 

문제

 



해답

간단히 생각해봤을 때, 없애야 하는 전깃줄의 최소 개수 = 최장 길이 부분수열을 구성하기 위해서 배제되어야 하는 요인의 개수

라고 생각할 수 있다.

따라서 이중 배열로 이어져 있는 전깃줄을 받고, A나 B에 대해서 정렬을 한 후에, 다른 한 전봇대가 구성할 수 있는 가장 긴 증가하는 부분수열의 개수를 총 전깃줄의 개수에서 빼주면 된다.

n = int(input())
s = [[0, 0]] * (n+1)

for i in range(1, n+1):
	s[i] = list(map(int, input().split()))

dp = [ 0 for _ in range(n+1) ]
s.sort()

for i in range(1, n+1):
	for j in range(1, i+1):
		if s[i][1] > s[j][1] and dp[i] < dp[j]:
			dp[i] = dp[j]
	dp[i] += 1
print(n - max(dp))