[DP] 병사 배치하기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40분 + a

1. 문제 설명

- 병사들의 전투력이 적힌 리스트가 입력으로 들어올 때 내림차순으로 병사들이 정렬되도록 하고자 한다. 가장 전투력을 높게 해서 병사들을 뽑고자 할 때, 병사들을 몇 명을 빼면 되는지 묻는 문제

2. 접근 방식

- 해당 문제는 특성상 정렬을 하면 안되고, 주어진 리스트를 그대로 활용해야 했다.

- 초기에는 점화식을 만들기 위해서 노력했으나 결국 그게 답이 아니라는 것은 해답을 보고서야 알았다.

- DP 중 유명한 알고리즘인 '가장 긴 증가하는 부분수열 문제'였다. 지금 문제는 감소하는 순서로 찾는 것이었기에 이를 역순으로 배열해야 '증가하는 부분수열 문제'가 된다.

- 가장 긴 증가하는 부분수열 문제의 점화식은 아래와 같다.

모든 0<=j < i에 대해, DP[i] = max(DP[i], DP[j] + 1) if array[j] < array[i] 

3. 코드

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

# 1차원 DP테이블 초기화
dp = [1] * n 
for i in range(1, n):
    for j in range(0, i): # 처음부터 i까지 끝까지 비교한다.
        if soldiers[j] < soldiers[i]:
            dp[i] = max(dp[i], dp[j]+1) #현재 i까지 입력된 최대값을 그냥 쓸건지 아니면 다른 흐름에 탑승할 것인지 결저
print(n-max(dp))

4. 코멘트

- '가장 긴 증가하는 부분수열 문제'의 경우 이중 반복문이 들어가는게 독특한 점이었던 것 같다.

- 해당 알고리즘의 경우 짧으면서도 중요하기 때문에 확실히 기억해야 할 필요가 있을 것 같다.

 - 이중반복문 부분에서 j의 range 값이 (0, i)라는 것과  조건문에서 뭐를 비교해야 하는지, max(dp[i], dp[j]+1) 세가지 부분이 해당 코드의 핵심인 것 같다. 아 추가적으로 1차원 테이블을 초기화하는 것까지 딱 기억하면 해당 알고리즘은 다 이해하고 넘어갈 것 같다. 아 리스트 뒤집는 것 까지...(이렇게 보니 사실 코드 전체네;;)