[Python] 병사 배치하기

문제

18353번: 병사 배치하기

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력

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

 

입력 예시

7
15 11 4 8 5 2 4

출력 예시

2

문제 풀이

• 가장 긴 증가하는 부분 수열 구하는 전형적인 다이나믹 프로그래밍 문제
• 증가하는 부분 수열이란 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분수열을 찾는 것
• 내림차순으로 주어진 배열을 뒤집어서 증가하는 부분 수열 구하면 답을 도출해낼 수 있다.
• 점화식은 아래와 같다.

# 0 <= j < i일 때
if dp[j] < dp[i] dp[i] = max(dp[i], dp[j] + 1)

코드

n = int(input())
array = list(map(int,input().split()))
# dp테이블 값 1로 초기화
dp = [1] * n
# array 뒤집어서 증가하는 부분수열 값 구하기
array.reverse()

# i,j 증가시켜 가며, 증가하는 부분수열의 최댓값 구하기
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))