[백준 18353번] 병사 배치하기

import sys
input = sys.stdin.readline

n = int(input())

data = list(map(int,input().split()))

dp = [1]*n

for i in range(1,n):
    for j in range(i):
        if data[i] < data[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(n - max(dp))

이번 문제는 병사의 수 N과 각 병사의 전투력 정보를 입력받은 뒤, 모든 병사를 내림차 순으로 정렬하되 남아있는 병사의 수가 최대가 되도록 만드는 문제이다.

 

해당 문제는 이전에 풀이했던 LIS 문제와 상당히 유사한 문제인데, 문제에서 열외시키는 방법으로 수행한다는 말 때문에 쉽게 떠올리지 못한 것 같다.

LIS 문제란 특정 조건을 만족하는 부분 수열 중에서 가장 길이가 긴 부분 수열을 구하는 문제인데, 이 문제에서는 증가하는 것이 아니라 내림차 순으로 수를 나열해야 하기 때문에 조건이 반대이다. (dp[i] = max(dp[i], dp[j]+1))

 

따라서 먼저 DP 테이블에 부분 수열의 길이를 1로 초기화한 뒤 2중 반복문을 사용하여 정렬된 병사의 수(부분 수열의 길이)를 채워나간 뒤에, 전체 병사의 수(n)에서 정렬된 병사의 수의 최대 값(max(dp))를 빼주면 풀이할 수 있다 :)