[BOJ] 병사 배치하기

---

코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

# 가장 긴 감소하는 부분수열 길이
d = [1]*n
for i in range(n):
    for j in range(i, -1, -1):
        if nums[i] < nums[j] and d[i] <= d[j]:
            d[i] = max(d[i], d[j]+1)

print(n-max(d))

결과

풀이 방법

• DP를 활용하여 해결하였다.
• x명의 병사를 열외시켜 가장 긴 감소하는 부분수열이 되도록 만들면 된다.
• 주어진 수열에서 가장 긴 감소하는 부분수열의 길이를 구하고, 전체 병사 수에서 빼면 정답이다.

---