[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 16 다이나믹 프로그래밍 문제 - Q34 병사 배치하기

1. 문제

---

2. 코드

n = int(input())

arr = list(map(int, input().split()))
arr.reverse()

dp = [1] * n

for i in range(1, n) :
  for j in range(0, i) :
    if arr[j] < arr[i] :
      dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))