이.코.테 병사배치하기

병사배치하기 문제

문제
-> 어떠한 수열이 주어졌을 때
그수열에서 최소한으로 열외시키면서 오름차순이 되게 해라

해결방법 1.
모든 경우의 수를 해보고 뭐가 최대인지
-> 시간복잡도 2000개 최대개수 이므로 2 ^2000 매우 비효율 또한 불가능

입력 예시)
7
15 11 4 8 5 2 4

해결방법2
lis알고리즘 활용 이때 lis 알고리즘은 설명은 여기 -> Title

lis알고리즘이 오름차순인것을 고려하여 적절히 응용해주면된다

코드에 녹여보면

#lis 알고리즘
#dp 점화식
#점화식은 d[i] = d[j] + 1 if(array[j] > array[i])  이때 (0 <= j <= i)

import sys
size = int(sys.stdin.readline().rstrip())

array = []
array = list(map(int, sys.stdin.readline().split()))

dp = [1] * (size + 1)

for i in range(size):
  for j in range(i):
    if array[j] > array[i]:
      dp[i] = max(dp[i], dp[j] + 1)
  

print(size - max(dp))