18353 - 병사배치하기

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

• LIS (가장 긴 증가하는 부분순열) 문제이다.

• LIS 에 핵심적인 점화식 개념을 써놓았다.

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

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

print(n - max(d))