동적(다이나믹) 프로그래밍

이것이 코딩테스트다 380p

 

기본 아이디어 -> 가장 긴 증가하는 부분 수열(LIS)

 

가장 긴 증가하는 부분 수열이란?

하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제

 

점화식

모든 0<=j<i에 대하여, max(D[i], D[j]+1) if array[j] < array[i]

 

=> 가장 긴 감소하는 부분 수열의 길이를 계산하는 문제로 간주하고, 입려긍로 주어진 원소의 순서를 뒤집은 뒤에 가장 긴 증가하는 부분 수열 문제를 풀 때의 점화식을 그대로 적용하면 해결할 수 있음

 

n=int(input()) #병사의 수 입력받기
array = list(map(int, input().split())) #병사의 전투력 입력받기
array.reverse() #순서를 뒤집어서 '가장 긴 증가하는 부분 수열' 문제로 변환

dp = [1]*n  # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화

#가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1,n): #i를 1부터 n-1까지 증가
	for j in range(0,i):
		if array[j] < array[i]:  #마지막 원소로 가지는 부분 수열의 최대 길이
			dp[i] = max(dp[i], dp[j] + 1) 

#열외시켜야 하는 병사의 최소 수를 출력
print(n-max(dp))