2021.3.18 [백준] 병사 배치하기

LIS 알고리즘

 

 

Q

 

www.acmicpc.net/problem/18353

18353번: 병사 배치하기

 

A

 

LIS 알고리즘을 사용하여야 쉽게 풀린다. 대신, 문제에서 내림차순으로 주어지기 때문에 sort로 오름차순 정렬하는게 편리하다.

 

나의 코드

 

n = int(input())
array = list(map(int, input().split()))

from bisect import bisect_left, bisect_right

dp = [array[0]]
array.reverse()

for i in range(n):
    if array[i] > dp[-1]:
        dp.append(array[i])
    else:
        idx = bisect_left(dp, array[i])
        dp[idx] = array[i]
print(n - len(dp))