[BOJ] 백준 2631번 문제 풀이 (Python)

1. 문제 풀이

주어진 수열을 오름차순으로 정렬하기위해 최소 몇 개의 수를 옮겨야하는지 찾는 문제였다.

LIS(최장 증가 부분 수열) 알고리즘을 적용해서 풀었다.

• ‘3 7 5 2 6 1 4’ 에서 최장 증가 부분 수열은 ‘3 5 6’ 이다. 1, 2, 4, 7을 옮기면 된다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())
nums = [int(input()) for _ in range(n)]
dp = [0] * n
for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i],dp[j])
    dp[i] += 1
print(n - max(dp))