백준_2565_전깃줄(DP)

n = int(input())
line = []
for _ in range(n):
    line.append([int(v) for v in input().split()])

line.sort(key = lambda x: x[0])
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if line[i][1] > line[j][1]:
            dp[i] = max(dp[i], dp[j]+1)

print(n - max(dp))

LIS로 구할 수 있는 문제이다.
A를 정렬 한 후 LIS를 구하면 교차하지 않는 전선의 최대 수를 구할 수 있다.

이렇게 구한 수를 N에서 빼면 교차하지 않기 위해 빼야하는 수를 구할 수 있다.