[Python] 백준 2631: 줄세우기

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

2631번: 줄세우기

1. 증가하는 부분수열중 가장 긴 수열은 3 7 5 2 6 1 4 이다.

2. 이 사이에 숫자를 오름차순으로 넣어주기만하면 되므로 ans = 아이들의 수 - 가장긴 증가하는 부분수열의 길이이다.

n = int(input())
chd = []
dp = [0 for _ in range(n)]
for i in range(n):
    chd.append(int(input()))
    for j in range(i):
        if chd[j] < chd[i]:
            dp[i] = max(dp[i], dp[j])
    dp[i] += 1
print(n-max(dp))