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

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

2565번: 전깃줄

코드

import sys
input = sys.stdin.readline
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[i][1] > arr[j][1]:
            dp[i] = max(dp[i], dp[j]+1)

print(n-max(dp))

 

<풀이방법>

dp로 현재 번호보다 적은 번호 중에 현재 연결된 전깃줄보다 높은 번호가 있으면 지우고 최장길이를 구함. 

그리고 항상 최장길이를 비교하여 업데이트 해서 저장해둔다.

 

dp문제는 항상 어려운 것 같다 ㅜㅜ