백준 병사 배치하기 코드 및 해설 (파이썬)

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

18353번: 병사 배치하기

 

'가장 긴 증가하는 부분 수열(LIS)'을 이용해 풀이했습니다. 이 문제는 오름차순이 아니라 내림차순을 요구하므로, 점화식의 부등호 방향만 바꾸어줬습니다. dp는 모두 1로 초기화하고, soldiers는 입력으로 받은 병사들의 전투력을 저장합니다.

점화식: 모든 0 <= j < i 에 대해, dp[i] = max(dp[i], dp[j]+1) if soldiers[j] > soldiers[i]

이후 dp의 최댓값을 구하면 가장 긴 내림차순 부분 수열의 길이가 되고, 이를 전체 병사의 수인 N에서 빼주면 문제에서 요구하는 열외해야 하는 병사의 수를 구할 수 있습니다.

 

import sys

# 병사 수
N = int(sys.stdin.readline())
# 병사들의 전투력
soldiers = list(map(int, sys.stdin.readline().split()))
dp = [1] * N

# 0 <= j < i 
# dp[i] = max(dp[i], dp[j]+1) if soldiers[j] > soldiers[i]
for i in range(N):
    for j in range(i):
        # 내림차순이면 
        if soldiers[j] > soldiers[i]:
            dp[i] = max(dp[i], dp[j]+1)

# max(dp)는 가장 긴 내림차순 부분 수열의 길이 
print(N - max(dp))