Study/코딩 테스트
2021.3.18 [백준] 병사 배치하기
NOredstone
2021. 3. 18. 16:43
LIS 알고리즘
Q
18353번: 병사 배치하기
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
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))