[Python] 전깃줄 - 백준

해당 글은 백준 2565번 문제 '전깃줄'을 다룬다.

문제

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

2565번: 전깃줄

 

설명

처음에는 해당 문제를 BFS로 모든 경우의 수를 구했었는데 시간초과가 떴다.

찾아본 결과 LIS(Longest Increasing Subsequence)와 DP를 합쳐서 해결하면 풀 수 있다고 한다..!

* 참고한 풀이영상 : https://www.youtube.com/watch?v=wn2dyWt9ml0 

 

코드

import sys
input = sys.stdin.readline

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

dp = [1]*(n+1)
for i in range(n):
    for j in range(i):
        if line[i][1] > line[j][1]:
            dp[i] = max(dp[i], dp[j]+1)
print(n-max(dp))