DP_병사 배치하기 풀이 암기

< 가장 긴 증가하는 부분 수열 >

* 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기
* [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기

# 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기
# [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기(가장 긴 증가하는 부분 수열)

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]: # array[2] < array[3]
            dp[i] = max(dp[i], dp[j] + 1) # dp[3] = max(dp[3], dp[2] + 1)

# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))