[BOJ] 2565번 전깃줄

A에서 i번째 매칭되는 B의 값을 A[i]라 할 때, A[i] < A[i+1] 이어야 전깃줄이 교차하지 않는다.
즉 A에 대해 오름차순으로 정리 한 후 A[i] 값들의 LIS를 구한 후, N에서 빼면 최소로 잘라야 할 전깃줄 수가 나온다.

LIS 구하는 알고리즘 최적은 $O(NlogN)$이지만 여기선 N의 범위가 빡세지 않아 $O(N^2)$으로도 통과된다.

N = int(input())
a_b_nums_list = [list(map(int,input().split())) for _ in range(N)]
b_nums = [x[1] for x in sorted(a_b_nums_list)]

# b_nums에 LIS 길이 구하고 N에서 뺀게 answer
dp = [1 for _ in range(len(b_nums))] # 하나만 있는 수열이면 길이 1이므로
for i in range(1,N):
  for j in range(0,i):
    if b_nums[j] < b_nums[i]:
      dp[i] = max(dp[i],dp[j]+1)

print(N-max(dp))