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

- N명의 병사 무작위로 나열

- 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치

- 특정 병사 열외, 남아있는 병사 최대가 되도록

- 열외시켜야 하는 병사의 수

 

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

# DP 테이블 초기화
dp = [1] * n

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

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