병사 배치하기

p. 380

 

n=int(input())

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

for i in range(1,n):
  for j in range(0,i):
    if array[j]<array[i]:
      d[i]=max(d[i], d[j]+1)

print(n-max(d))

 

reverse를 한 후 '가장 긴 증가하는 부분 수열' 아이디어를 활용한다.