[알고리즘] 백준 - 1365 (꼬인 전깃줄) / 파이썬

import sys
import bisect

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

LIS = [num[0]]
for n in num[1:]:
    if LIS[-1] < n:
        LIS.append(n)
    else:
        tmp = bisect.bisect_left(LIS, n)
        LIS[tmp] = n

print(N-len(LIS))

최장 증가 수열 LIS 를 구해서 전체 크기에서 빼주면 된다. 2중 for문으로 하면 $O(N^2)$ 이라서 이분탐색으로 수행하였다.
결과 배열은 정확한 LIS는 아니지만 길이만 구하면 되기 때문에 빠르게 풀 수 있었다.