문제풀이/DP
[파이썬] [DP] 백준 18353 병사 배치하기
승무_
2022. 1. 24. 11:48
링크
https://www.acmicpc.net/problem/18353
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
코드
import sys
f = sys.stdin.readline
n = int(f())
a = [int(x) for x in f().split()]
dp = [1] * n
# 앞쪽에 있는 값이 항상 뒤보다 커야함
# 남아있는 병사 수가 최대가 되어야 함
for i in range(n):
for j in range(i):
if a[i] < a[j]:
dp[i] = max(dp[i], dp[j]+1)
print(len(a) - max(dp))