[백준] 1365 꼬인 전깃줄, python

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

 

 

 

 

 

전깃줄이 꼬이지 않기 위해선 오름차순 순서대로 연결해야 한다.

입력된 케이스에서 가장 긴 증가하는 부분 수열을 구하고 그 외의 전깃줄을 잘라내면 된다.

 

 

 

LIS(가장 긴 증가하는 부분 수열), python

LIS(가장 긴 증가하는 부분 수열), python

 

 

 

 

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# 가장 긴 증가하는 부분 수열을 구하는 문제이다.

lis = []
for x in arr:
    if not lis:
        lis.append(x)

    if lis[-1] < x:
        lis.append(x)
    else:
        index = bisect_left(lis,x)
        lis[index] = x

l = len(lis)

print(n - l)