[파이썬] 백준 2631 줄 세우기

조합을 이용했고 당연히 메모리 초과가 났다. 힌트 글에서 최대 증가 수열을 구하면 된다고 했고 저번에 풀었던 풀이지만 기억이 안났다. 이제는 이해가 됐고, 이를 이용해서 문제를 풀었다.

import sys
from collections import deque
from itertools import combinations
 
N = int(input())
 
k = [ ]
 
for i in range(N):
    k.append(int(input()))
 
 
# 앞에서 부터 최대 증가 하는 수 찾기
'''
def checks(k):
 
    for i in range(0,len(k)-1):
        if k[i]>k[i+1]:
            return False
    return True
 
check = 0
 
for i in range(N,-1,-1):
 
    if check == 1:
        break
 
    m = list(combinations(k,i))
 
    for j in range(0,len(m)):
        if checks(m[j]) == True:
            print(len(k)-len(m[j]))
            check = 1
            break
 
'''
 
dp = [1]*N
 
for i in range(len(k)):
    for j in range(i):
        if k[i] > k[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(len(k)-max(dp))