[백준 2631번] 줄세우기

n = int(input())

data = []

dp = [1]*n

for i in range(n):
    data.append(int(input()))

for i in range(n):
    for j in range(i):
        if data[i] > data[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(n - max(dp))

이번 문제는 임의의 순서로 세워진 번호를 번호 순서대로 배치하기 위한 최소한의 이동횟수를 구하는 문제이다.

 

번호를 옮기는 횟수를 최소화하기 위해서는 번호 순서대로 세워져있는 어린이들을 최대한 많이 고정시키고 나머지만 이동시켜야 한다. 즉, 가장 긴 증가하는 부분수열 LIS(Longest Increasing Subsequence)의 길이를 구하고 이를 전체 어린이 수에서 빼주어야 한다.

 

LIS를 다룬지 오래되어 기억이 잘 나지 않았는데, 다시 한번 복습할 수 있는 문제였다 :