#409 백준 파이썬 [2631] 줄세우기 - LIS

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

 

SOLUTION

최장 증가 부분 수열 (LIS : Longest Increasing Subsequence)문제이다.

 

간단하게 말하자면 먼저 답이 될 수열을 dp = [] 로 정의한 뒤

for문으로 children 리스트 앞쪽부터 검사를 진행한다.

 

if: 현재 값이 수열에서 가장 크다면

--> dp의 가장 뒤에 값을 추가

else: 아니라면

--> 자신보다 큰 수 중 최솟값과 대치(이진탐색 이용)

 

이런식으로 증가하는 최장 길이의 부분 수열의 길이(리스트 구성은 틀림)를 알아낼 수 있다.

이 방법으로 시간복잡도 O(nlogn)에 가장 긴 dp의 길이를 알아낼 수 있다.

PYTHON CODE

from bisect import bisect_left

children = []
for _ in range(int(input())):
    children.append(int(input()))

dp = []
for i in children:
    k = bisect_left(dp, i)
    if len(dp) <= k:
        dp.append(i)
    else:
        dp[k] = i
print(len(children) - len(dp))