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

문제

 

 

 

 

이 문제를 처음 봤을 때는 솔직히 도대체 어떻게 풀어주어야할 지 감이 안잡혔다....

a번 번호를 기준으로 오름차순 정렬은 해봤는데 그 이후로 진도가 안나가서 구글링을 해봤고 LIS알고리즘에 대해서 알게 되었다.

 

 

LIS알고리즘 관련 내용

https://4legs-study.tistory.com/106

최장 증가 수열 (LIS, Longest Increasing Subsequence)

 

 

 

 

 

이 설명을 보면 뭔가 이해는 되는데 그래서 이 문제에 어떻게 적용 해야하는건가 의문이 들 수 있다.

 

이때 답은 n-최장증가 수열의 길이가 된다

 

이게 대체 어떻게 이렇게 되는지 이해가 안될 수도 있는데 설명하자면 우리가 구하는건 선을 교차하지 않게 하도록 할 때 제거해야하는 전선의 "최소" 개수 이다.

 

그러니 교차하지 않는다 =  증가 수열   이 되고 전선의 개수를 최소로 제거할 때는 증가수열이 최장 증가수열이 될 때 이다.(전선을 최소로 제거하면 남는 증가 수열은 최장증가수열이 되기 때문)

 

그래서 LIS알고리즘 대로 최장증가수열의 길이를 구해준 후 답은 n-max(dp)   로 해주면 된다.

 

 

 

코드

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

ab.sort(key = lambda x:x[0])

dp = [1] * n

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

print(n-max(dp))