[Python/백준]전깃줄(DP)

 

 

 

 

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

2565번: 전깃줄

 

 

왼쪽 전봇대 번호 순으로 정렬을 한 후 

오른쪽 전봇대의 가장 긴 증가하는 순열의 길이를 구하면 된다. 

 

 

구한 순열의 길이는 겹치지 않고 설치할 수 있는 전깃줄의 길이이므로 

전체 전깃줄의 개수에서 구한 길이를 빼주면 제거해야하는 전깃줄의 길이가 나온다. 

 

 

 

 

 

코드 : 

if __name__=="__main__" :
    n = int(input())
    arr = [list(map(int,input().split()))for _ in range(n)]
    arr.sort(key = lambda x : x[0])
    
    dp = [1]*n
    for i in range(n) :
        for j in range(i) :
            if arr[j][1]< arr[i][1] and dp[i] < dp[j]+1 :
                dp[i] = dp[j]+1 
                
    print(n - max(dp))