![[2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fl6lMj%2FbtsjllMtUw2%2FeADPMDNFGoYvzT4aKJXbnk%2Fimg.png)
728x90
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
분석
정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌
풀이
import sys
from bisect import bisect_left
input=sys.stdin.readline
n = int(input())
arr=[]
for _ in range(n):
arr.append(int(input()))
d=[]
for i in arr:
k = bisect_left(d, i)
if len(d) == k:
d+=[i]
else:
d[k]=i
# print(d)
print(n-len(d))
728x90