[BOJ] Python 백준 줄세우기(2631)

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

 

가장 긴 증가하는 부분 수열의 심화 문제이다.

dp를 통해 가장 많이 증가하는 폭을 찾고, 증가하는 폭을 제외한 나머지 값들은 값을 이동 시켜야하므로, (N-가장 긴 증가하는 폭) 정답이다.

import sys
input = sys.stdin.readline

N = int(input())

dp = [1] * N
s = []
for _ in range(N):
    s.append(int(input()))

for i in range(N):
    for j in range(i):
        if s[j] < s[i]:
            dp[i] = max(dp[i], dp[j]+1)


print(N-max(dp))

 

회고.

처음 문제를 접근했을때는 dp라는 감도 못잡았다. 또한, 가장 긴 증가하는 부분 수열을 통해 이동하지 말아야할 값을 찾고 이동하는 값을 N으로 빼줌으로써 정답을 찾는 과정은 실제로 접했을때 풀 수 있을까 싶다....