[백준][최장증가수열] 줄세우기

줄세우기

 

• 내 풀이
  • 정렬된 아이들은 그대로 두고 아닌애들을 옮겨야 함
  • 최장증가수열 길이 구해서 정렬된 아이들 수를 구하기
    • 전체 아이들 수 - 정렬된 아이들 수

n = int(input())
childs = [int(input()) for _ in range(n)]
dp = [1 for _ in range(n)]
for i in range(1, n):
    for j in range(i-1, -1, -1):
        if childs[j] < childs[i]:
            dp[i] = max(dp[i], dp[j]+1)
        else:
            continue

print(n-max(dp))