[동적계획법] 백준 18353번 '병사 배치하기' (Python)

<문제 링크>

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

18353번: 병사 배치하기

---

<문제 풀이>

1. 가장 긴 증가하는 부분 수열 알고리즘 이용하여 풀 수 있음

 

<코드>

n = int(input())
array = list(map(int,input().split())
array.reverse()

dp = [1] * n

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))

 

<고쳐야 할 점>

• 가장 긴 증가하는 부분 수열 알고리즘 기억하기
• 복습 알고리즘