BOJ 2631 : 줄세우기 (Python)

문제

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

2631번: 줄세우기

 

 

코드

n = int(input())
array = [0] * n
dp = [1] * n

for i in range(n):
    array[i] = int(input())

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

 

 

풀이

 

번호 순서대로 줄을 세우기 위해 옮기는 학생 수가 가장 적은 경우를 찾기 위해서는 현재 배열에서 순서대로 배치되어 있는 학생 수가 몇명인지 찾으면 된다.

→ 순서대로 배치되어 있는 학생들은 그대로 두고 나머지 학생들만 옮기면 되기 때문이다.

 

여기서 '순서대로' 란 숫자가 증가하는 순서이므로 LIS(가장 긴 증가하는 부분 수열)를 찾아서 전체 학생 수에서 LIS 를 빼주면 정답이 된다. 

 

LIS(Longest Increasing Subsequence)

• 점화식 : 모든 0 ≤ j < i 에 대하여, D[i] = max(D[i], D[j]+1) if array[j] < array[i]