99클럽 코테 스터디 31일차 TIL + DP

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

import sys
input = sys.stdin.readline

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

dp = [1] * n
for i in range(n):
    for j in range(i):
        if lines[j] < lines[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(n-max(dp))

• 결국 오름차순으로 정렬되기까지의 최소 이동 횟수를 정해야한다.
• 가장 큰 증가하는 부분 수열을 구하면 그 사람은 올바르게 줄 서있는 것이기 때문에 그 나머지 값을 구하면 된다.