문제

풀이

풀이 아이디어

가장 긴 증가하는 부분 순열 문제
D[i] = array[i]를 만지막 원소로 가지는 부분 순열의 최대 길이
모든 $0<=j<i$ 에 대하여
$D[i]=max(D[i],D[j]+1)$ if $array[j]<array[i]$

예시

[10 20 10 30 20 50] 을 증가하는 부분순열로 만들고싶을때

남아있는 값 중 가장 큰 값이 가장 긴 증가하는 부분 순열의 길이
이 예시에서는 4가 최장 길이가 된다.

이 문제에선

• 가장 전투력이 높은 병사가 앞에 오므로, 원소의 순서를 거꾸로 뒤집은 다음
• '가장 긴 증가하는 부분순열 문제'의 점화식 적용한다

코드

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '가장 긴 증가하는 부분 순열' 문제로 변환
array.reverse()

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

# 가장 긴 증가하는 부분 순열(LIS) 알고리즘 수행
for i in range(1, n) :
	for j in range(0, i) :
		if array[j] < array[i] :
			dp[i] = max(dp[i], dp[j]+1)

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