유형 파악 및 구현
예를 들어, [15, 11, 4, 8, 5, 2, 4]가 있을 때, 오른쪽으로 갈수록 수를 크게 만들면서, 리스트 내의 요소가 가장 많은 경우를 구하는 것이다.
이는 전형적인 다이나믹 프로그래밍의 문제 중 하나인 '가장 긴 증가하는 부분 수열 문제'이다.
[15, 11, 4, 8, 5, 2, 4]
dp 리스트는 아래와 같은 방식으로 채워진다.
4 - [1] : 마지막 요소 뒤에는 아무 요소가 없다. -> dp(n-1)
2- [1] : 2의 뒤에는 2보다 작은 요소가 없다. -> dp(n-2)
5 - [2] : 5의 뒤에는 2 or 4를 넣을 수 있다. -> dp(n-3) = dp(n-2) + 1 or dp(n-1) + 1
8 - [3] : 8의 뒤에는 (5, 2) or (5, 4)를 넣을 수 있다.
...
참고로 dp리스트의 의미를 정의해보자면
dp[i] 는' i ~ n의 요소에서 만들 수 있는 리스트의 최대길이' 정도 될 것 같다.
코드
n = int(input())
soldiers = list(map(int,input().split()))
dp = [1]*(n)
for i in range(n-2, -1, -1):
for j in range(i+1, n):
if soldiers[j] < soldiers[i]:
dp[i] = max(dp[i], dp[j]+1)
print(n-max(dp))
