[python 파이썬] 백준 2565번 파이썬

2565번: 전깃줄

 

이 문제는 정렬부터 했어야했는데 정렬을 생각해내지 못했다. 

 

풀이법

1. A의 위치번호로 정렬하기

2. A에 연결된 B의 위치번호가 현재 가리키는 위치번호보다 위에 위치한 전깃줄의 최대 갯수에 +1 

3. 전체에서 최대개수빼기

 

n = int(input())

line=[list(map(int,input().split())) for _ in range(n)]
line.sort(key=lambda x :x[0])
dp=[0]*501

for s, d in line:
  dp[d]=max(dp[:d])+1

print(n-max(dp))