[dp/백준] 2565번: 전깃줄

-문제:https://www.acmicpc.net/problem/2565

이전에 싸피 준비할 때 들었던 유튜브 강의에서 같은 내용을 공부한 적이 있어서 문제 보자마자 가장 긴 증가하는 부분수열 문제라는 것을 알았다. 

주어진 정보를 0열을 기준으로 sort한 다음 1열 값과 dp값을 이용해서 가장 긴 부분수열의 길이를 구한다음,

전체 가짓수에서 빼주면 답이다. 

한번에 맞혔던 문제!

-정답풀이: 

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
data.sort()
dp=[0]*501
for i in range(n):
    for j in range(i+1):
        if data[j][1]<data[i][1] and dp[j]>dp[i]:
            dp[i]=dp[j]
    dp[i]+=1
x=max(dp)
print(n-x)