[알고리즘] 다이나믹 프로그래밍(LIS) - 병사 배치하기

출처 : 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

병사 배치하기 

( 직접 못 풀어서 답안 예시를 공부 )

 

N명의 병사가 무작위로 나열, 각 병사는 특정한 값의 전투력을 보유

병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치

다시 말해서, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다.

그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶다.

 

첫째 줄에 N이 주어진다. (1<=N<=2000)

둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 주어진다.

각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

 

첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수 출력

 

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

 

시간 제한 1초이기 때문에 O(N**2) 이하의 알고리즘으로 설계가 필요하다.

---

아이디어 : 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)

- 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열

- D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

출처 : 동빈나 유튜브

--> 입력 받은 병사 정보의 순서를 뒤집은 후 가장 긴 증가하는 부분 수열을 찾는 문제로 치환

 

 

답안 예시

N = int(input()) # 1 <= N <= 2000
soldier_list = list(map(int, input().split()))
soldier_list.reverse()
print(soldier_list)

DP_table = [1]* N

for i in range(1, N):
    for j in range(i):
        if soldier_list[i] > soldier_list[j]:
            DP_table[i] = max(DP_table[j]+1, DP_table[i])

print(N-max(DP_table))