[2631] 줄 세우기 (최장증가수열, LIS, 2중 for문)

2631번: 줄세우기

 

 

분석

정렬되어 있는 어린이 빼고 나머지를 이동하므로 LIS의 길이를 구한 뒤 N에서 뺌

 

풀이

import sys
input=sys.stdin.readline

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

dp = [0 for _ in range(n)]
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# print(dp)
print(n - max(dp))