백준 2565 전깃줄 (파이썬)
접근방식
- 전깃줄 리스트를 A 전봇대를 기준으로 정렬을 해준 후 B전봇대에서 가장 긴 증가하는 부분수열을 구하면 된다.
- 가장 긴 증가하는 부분수열 문제 해설은 아래에서 확인해볼 수 있다.
https://ataraxiady.github.io/dev/2021/03/30/dev-boj-1_11053/
파이썬 코드
import sys
n = int(sys.stdin.readline())
arr = []
arr_b = []
dp = [0 for i in range(n)]
for _ in range(n):
arr.append(list(map(int, sys.stdin.readline().split())))
arr.sort(key=lambda x:x[0])
for i in range(n):
arr_b.append(arr[i][1])
for i in range(n):
for j in range(i):
if arr_b[i] > arr_b[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] = dp[i] + 1
print(n - max(dp))
