백준 2565번 "전깃줄"

문제

백준 2565번 '전깃줄'

풀이

LIS 응용문제.

전봇대 하나를 정렬해주고 다른 전봇대에서 LIS를 구하면 된다.
나머지는 11053번을 참조하자.

Python 코드

import sys

input = sys.stdin.readline

n = int(input())
arr=[]

for _ in range(n):
  arr.append(list(map(int, input().split())))

arr.sort()

k = [1]*n

print(arr)

for i in range(1, n):
    for j in range(i):
        if arr[j][1] < arr[i][1]:
            k[i] = max(k[i], k[j]+1)

print(n-max(k))