[백준] 18353 - 병사 배치하기 (DP)

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

18353번: 병사 배치하기

n = int(input())
arr = list(map(int, input().split()))
 
answer = [1] * n
 
for i in range(n):
    for a in range(len(arr[:i])):
        if arr[i] < arr[a] and answer[i] < answer[a] + 1:
            answer[i] = answer[a] + 1
 
print(n - max(answer))

O(n^2) 시간복잡도로 접근한 DP 문제이다.

방식을 다르게 하면 nlogn까지 줄일 수 있을 것 같은데, n이 최대 2000이라서 그냥 n^2으로 했다.

검사하는 병사의 전투력을 앞에 있는 병사들의 전투력과 비교하면서, 전투력이 더 작으면 해당 병사까지의 최대 수열 길이 + 1을 저장한다.