34_병사 배치하기

18353번: 병사 배치하기

DP 문제다.

점화식을 생각해내지 못해서 풀지 못했다.

 

---

풀이 코드

# 18353번: 병사 배치하기
n = int(input()) # 병사의 수
arr = list(map(int, input().split())) # 전투력
arr.reverse()

dp = [1] * n # dp 테이블

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, len(arr)):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

# 열외시켜야 하는 병사의 최소 수 출력
print(n - max(dp))

 

이 문제는 전형적인 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)로 알려진 전형적인 DP 문제다.

 

가장 긴 증가하는 부분 수열이란, 예를 들어

array = [10, 20, 10, 30 ,20 ,50] 이라는 수열이 있다고 할 때, 

가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]이 될 것이다.

 

dp[i] = array[i]를 마지막 원소를 가지는 부분 수열의 최대 길이라고 정의하면,  가장 긴 증가하는 부분 수열의 길이를 계산하는 점화식은 다음과 같다.

 

모든 0 <= j < i에 대하여, dp[i] = max(dp[i], dp[j] + 1) if array[j] < array[i]

 

 

우리가 풀어야 할 문제는 병사를 배치할 때, 전투력이 가장 높은 병사가 앞쪽으로 오도록 내림차순 배치를 하고자 한다.

따라서 이 문제는 가장 긴 감소하는 부분수열의 길이를 계산하는 문제로 간주하고, 입력으로 받은 리스트의 순서를 뒤집은 후, 

가장 긴 증가하는 부분 수열의 길이를 구하는 점화식을 그대로 적용한다.

그대로 적용한 후, dp 테이블의 최댓값이 가장 긴 부분 수열의 길이이므로, 

전체 병사 수 - 병사가 배치될 수 있는 가장 많은 병사수를 해주면 답이 나온다.

 

 

---

LIS 관련 문제를 풀어봐야겠다.