problem-2565

과정
1. input을 튜플로 받은 후, 정렬
2. 전선이 꼬이지 않기 위해서는 튜플[1]의 항목들이 모두 오름차순으로 정렬되어야함 -> 가장 긴 부분수열 찾기
3. d[n]은 n이 마지막(가장 큰) 수 일때 최대 길이의 부분수열
4. d[i]=max(d[i],d[j]+1) -> j가 i보다 작은 수이며 이 둘을 비교하여 가장 큰 값을 저장
5. 필요한 값: 없애야하는 전선줄 -> 구하는법: 원래 전선줄 n - 가장 긴 부분수열 max(d)

n=int(input())
line=[]
for i in range(n):
    a,b=map(int,input().split())

    line.append((a,b))
line.sort()
l=[0]
for i in line:
    l.append(i[1])

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

print(n-max(d))

time:30분
resolved:x