18353 - 병사 배치하기

 

 

---

 

문제

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

18353번: 병사 배치하기

 

풀이

가장 긴 감소하는 부분 수열이랑 문제가 완전히 똑같다.

(가장 긴 증가하는 부분 수열의 반대로 https://whiporithm.tistory.com/11 )

n에서 가장 긴 감소하는 부분 수열의 길이를 빼주면 정답이다.

 

코드

n = int(input())
d = [1] * n
wars = list(map(int, input().split()))

for i in range(n):
    for j in range(i):
        if wars[j] > wars[i]:
            d[i] = max(d[j]+1, d[i])

print(n  - max(d))