[백준/Python] 2631 줄 세우기

문제 링크

2631번: 줄세우기

 

문제 풀이

• 이 문제는 '가장 긴 증가하는 부분 수열' 문제로 생각할 수 있다.
• 옮겨지는 아이들의 수가 최소가 되려면 현재 번호대로 줄 서 있는 아이들 수가 최대가 될 때, 그렇지 않은 나머지 아이들이 움직이면 된다.
• 따라서, 전체 아이들 수에서 번호가 증가하는(차례로 있는) 아이들 수를 제외하면 된다.

 

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
children = [int(input()) for _ in range(n)]

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

print(n - max(dp))