[BOJ] 2565 전깃줄 - python(파이썬)

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

2565번: 전깃줄

 

입력받은 값을 a를 기준으로 정렬한 이후

b에 해당하는 값들 중 차례대로 증가하는 부분수열을 찾으면 교차하는 전깃즐이 없는 것들이 된다.

 

그래서 (전체 전깃줄의 수) - (가장 긴 증가하는 부분수열) 을 하면 답이 된다.

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

data.sort(key = lambda x:x[0])
dp = [1] * n

# 가장 긴 증가하는 부분수열 찾기
for i in range(n):
    for j in range(i):
        if data[i][1] > data[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

---

https://github.com/wwan13

wwan13 - Overview