[Python] 백준 2631_ 줄세우기

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.
(예제)
7
3
7
5
2
6
1
4
위 예제는 다음과 같이 옮겨 줄 세울 수 있다.
즉, 가장 긴 증가하는 부분수열을 구해서 그 길이를 n에서 빼주면 된다.

1.DP정의

• dp: i번째까지 증가했을때 수열의 최대 길이
• d = [1]*n 으로 초기화 -> 최소 현재 부터 시작하는 길이 1인 수열이 존재 가능하므로
  

2. 점화식 찾기

d[i] = max(d[j]+1, d[i])
j = i앞의 index중 a[i]보다 a[j]가 작을 경우

3. 코드

import sys
input = sys.stdin.readline

n = int(input())

d = [1]*(n+1)
num = [0]
for i in range(n):
    num.append(int(input()))

#가장 긴 증가하는 수열 찾기 
for i in range(1,n+1):
    for j in range(1,i):
        if num[j]<num[i]:
            d[i]=max(d[i],d[j]+1)

#n- 긴 증가하는 부분수열의 길이 
print(n-max(d))