병사 배치하기

풀이

 이 문제는 '가장 긴 증가하는 부분 수열'로 알려진 전형적인 dp 문제의 아이디어와 같다. 문제에서는 내림차순 배치가 조건이었지만 편의상 reverse 함수를 사용해 오름차순으로 바꿔 풀었다. 입력조건(1<= n <= 2000)을 봤을 때 대략 O(n^2) 정도의 시간복잡도까지는 허용되므로 O(nlogn)인 정렬 정도는 괜찮다고 생각했다.

n = int(input())

data = list(map(int, input().split()))
dp = [1 for _ in range(len(data))]

data.reverse()

for i in range(n):
    for j in range(i):
        if data[j] < data[i]:
            dp[i] = max(dp[j] +1, dp[i])
print(n-max(dp))

시간복잡도 : O(n^2)