[백준 1365번] 꼬인 전깃줄 (Python3)

from bisect import *

N = int(input())
seq = [*map(int,input().split())]
DP = [0]
for n in seq:
  if n>DP[-1]:
    DP.append(n)
  else:
    DP[bisect_left(DP,n)] = n

print(N+1-len(DP))

전깃줄 - 2 [백준 2568번] 전깃줄 -2 (Python3) (tistory.com) 문제의 하위호환 문제

N과 LIS 길이의 차를 출력해주면 된다.

 

 

여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.