BOJ : 1835 병사배치하기 (파이썬)

문제

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

18353번: 병사 배치하기

이 문제는 다이나믹 프로그래밍으로 풀 수 있다.

이중 for 문을 이용해 첫번째 for문으로는 비교해야할 요소를 하나 정하고 두번째 for문으로 비교해야할 요소들의 전을 한번씩 탐색해주면서 +1 해줘서 d를 채워 나가는 식으로 풀 수 있다.

소스코드

import sys

n = int(sys.stdin.readline())

d = [1] * (n+1)

lst = list(map(int, sys.stdin.readline().split()))

for i in range(1,n) :
    for j in range(0,i) :
        if lst[i] < lst[j] : 
            d[i] = max(d[i] , d[j] + 1 )


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