[백준] 18353 병사 배치하기

유형 : DP(다이나믹 프로그래밍)

배열을 뒤집어서 가장 긴 증가하는 수열을 찾는다 

 

예전에 풀었던 문제 11722 가장 긴 감소하는 부분 수열과 똑같은 dp 문제이다. 다만 이번 문제에서는 제외할 병사의 수를 출력해야 하므로

n - dp의 최댓값 (= 가장 긴 수열의 길이) 를 출력해주어야 한다.

 

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열 문제라고 생각하고 풀면 된다 ! 

n = int(input())
a = list(map(int, input().split())) # 전투력
a.reverse()
dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + 1)


print(n - max(dp))