병사 배치하기

📌문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치 하고자 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야하는 병사의 수를 출력하시오.

 

📌풀이

가장 긴 감소하는 부분 수열의 길이를 계산

하나의 수열이 주어졌을 때 값들이 감소하는 형태의 가장 긴 부분 수열을 찾음

 

📌코드

n = int(input())
array = list(map(int, input().split()))
# 가장 긴 증가하는 부분 수열 문제로 변환
array.reverse()

dp = [1] * n

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))

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬