백준 - 2565 : 전깃줄 (G5)

🏷️ python 🏷️ boj

수정일 : 2024-11-15


 1N = int(input())
 2L = [list(map(int, input().split())) for _ in range(N)]
 3L = [i[1] for i in sorted(L)]
 4dp = [0]*N
 5for i in range(N):
 6    dp[i] = 1
 7    for j in range(i):
 8        if L[j] < L[i]:
 9            dp[i] = max(dp[i], dp[j]+1)
10
11print (N-max(dp))
  • LIS를 이용하는 문제