[Baekjoon] 2565번 : 전깃줄

골드 5

2565번: 전깃줄

 

문제 풀이

전깃줄의 순서를 리스트로 입력받아 한쪽의 전기줄을 기준으로 정렬한다.

나머지 한쪽에 연결되는 전기줄의 번호가 증가하면 교차하지 않는다.

따라서 나머지 한쪽에 연결되는 번호들의 가장 긴 증가하는 수열을 찾고 전체 전기줄 수에서 빼면 삭제해야 할 전기줄의 최소 개수를 구할 수 있다.

 

 

코드

n = int(input())
nums = []
for i in range(n):
    nums.append(list(map(int, input().split())))
nums.sort()

dp = [0] * n
for i in range(n):
    for j in range(i):
        if nums[j][1] < nums[i][1] and dp[j] > dp[i]:
            dp[i] = dp[j]
    dp[i] += 1

print(n - max(dp))