[파이썬 / 백준 2565번] 전깃줄

https://www.acmicpc.net/problem/2565

 

이게 어떻게,, 어떻게,, 어떻게 LIS 응용인지 모르겠지만,,

 

처음에는 제일 겹쳐있는게 많은 선 부터 끊고,

그 선이 없는 새로운 리스트를 반환해서 그 다음 겹치는게 많은 선을 끊고,

그리고 겹치는게 없어질 때까지 하는것으로 코드를 짰었는데,

 

겹치는 수가 같은데 경우에 수가 다를 수도 있다는 생각을 하니 막막..

 

다른 분 풀이를 봤는데

솔직히 잘 이해가 안된다.. 그냥 받아들여야지...

이해가 될랑 말랑..

N=int(input())
nl=[list(map(int,input().split())) for _ in range(N)]
nl=sorted(nl,key=lambda x:x[0])
dp=[1]*N
for i in range(N):
    for j in range(i):
        if nl[i][1]>nl[j][1]:
            dp[i]=max(dp[i],dp[j]+1)

print(N-max(dp))