[BOJ] 2565번 전깃줄 문제 - Python

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

생각보다 단순한 문제였다.

 

LIS(Longest Increasing Sequence, 가장 긴 증가하는 부분수열)를 이용하는 문제다.

 

몇개 빼면 제일 똑바로 연결되어있냐? 이건데,

 

서로 교차안한다 -> 한쪽을 기준으로 오름차순으로 연결되어있다. -> 가장 긴 증가하는 부분수열을 찾아라.

 

이걸 그리 해맸다.

 

왼쪽이든 오른쪽이든 한쪽 기준으로 정렬을 해서, LIS를 찾으면 된다.

 

from sys import stdin
input = stdin.readline

N = int(input())
numbers = []
for _ in range(N):
    numbers.append(list(map(int, input().rstrip().split())))

numbers.sort(key=lambda x:x[0])

DP = [0] * N
DP[0] = 1

for i in range(1, N):
    for j in range(i+1):
        if numbers[i][1] > numbers[j][1] and DP[j] > DP[i]:
            DP[i] = DP[j]
    DP[i] += 1

print(N - max(DP))