[이코테] 다이나믹 프로그래밍_병사 배치하기 (python)

문제

나의 풀이

1. 성공

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i): # 0 <= j < i 
        if a[i] < a[j]: # 내림차순이기 때문에
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp)) # n - 가장 긴 내림차순 부분 수열의 길이 

: 처음에는 이게 뭔가 싶다가, 결국 증가하는 길이를 구하면 되는거라서..! 이해만 하면 쉽게 풀리는 문제.