[백준-18353] 병사 배치하기 / Python

18353번: 병사 배치하기

import sys

input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))
d = [1] * n

for i in range(n):
    for n in range(len(data[:i])):
        if data[i] < data[n] and d[i] < d[n] + 1:
            d[i] = d[n] + 1

print(len(d) - max(d))

 

해설

dp 문제. 생각해야하는 경우의 수가 좀 있어서 애를 먹었다.

우선 이중포문으로 현재 값과 이전 값들을 비교해줘야 한다. 현재 값이 이전 값보다 작고 dp에 저장된 값이 그 이전 값 인덱스의 dp 값 + 1보다 작으면 현재 dp 값을 이전 dp 값에 1 더해준다.