[python] 백준 2631 줄세우기

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

2631번: 줄세우기

 

문제 해결

•  LIS (Long Increase sequence) 구하는 문제
•  가장 긴 증가하는 수열이 만들어 진 부분 수열을 구한다음 그 원소들을 빼고 나머지를 필요한 곳으로 옮기면 되는 것이다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
A = [0]+[int(input()) for _ in range(n)]
dp = [0 for _ in range(n+1)]
M = 0 # 최대 증가 길이 수열 (LIS)
for i in range(1,n+1):
    for j in range(1,i):
        if A[i] > A[j]:
            M = max(M,dp[j])
    dp[i] = M + 1 # 원소 i까지 포함해야하므로
    M = 0 # reset
print(n-max(dp)) # 이미 만들어진 LIS빼고 나머지 원소를 옮기면 된다.