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

문제

https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

---

문제 요약

N명의 병사들이 무작위로 나열되어 있고, 각 병사들은 전투력을 갖고 있다.

 

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

 

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

---

코드

N = int(input())

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

dp = [1] * N
# dp[i]는 i 인덱스까지 내림차순한 병사의 최대 수


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

print(N - max(dp))

---

코드 설명

1. i 인덱스까지 가장 긴 감소하는 부분 수열의 개수(병사 최대 수)를 저장하는 메모이제이션 테이블 dp를 생성한다.

 

2. 0번 인덱스부터 i-1번 인덱스까지 접근하며 이전 인덱스 값 (arr[j]) 보다 자신의 인덱스 (arr[i]) 값이 작으면 dp[j]값에 1을 더한 값과 dp[i]값을 비교하여 큰 값으로 갱신한다.

+ dp[j]에 1을 더한 값:  j까지의 가장 긴 감소하는 부분 수열에 자기 자신을 추가한 부분 수열의 개수

 

3. N - (dp 배열 중 가장 큰 값)을 출력한다.

+ 열외해야 하는 병사의 수 = 전체 병사의 수 - 남아 있는 병사의 수