[백준] 18353 파이썬(python) : 병사 배치하기

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

18353번: 병사 배치하기

 

 

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1]*2001 #1
for i in range(1, n): #2
    for j in range(0, i): #3
        if arr[j] > arr[i]: #4
            dp[i] = max(dp[i], dp[j]+1) #5
print(n-max(dp)) #6

 

#1 : 모든 병사들의 최소 길이는 혼자일때이므로 1로 초기화

#2 : 1부터 시작

#3 : dp값 갱신을 위해 0 <= j < i 범위 설정

#4 : 내림차순이니까 arr[j] > arr[i]일때 dp값 갱신

#5 : 가장 긴 증가하는 부분수열 점화식(여기서는 감소하는 부분수열)

#6 : 열외해야하는 병사 수를 출력하는 것이 문제의 요구조건이니까 전체수 n에서 가장 최대의 부분수열 max(dp)를 빼면 열외하는 최소 병사 수를 구할 수 있다.

 

 

---

11053번 가장 긴 증가하는 부분수열   

bisect는 오름차순일때를 기준으로 올바른 인덱스를 찾아준다. bisect포스팅