BOJ 18353. 병사 배치하기 (Silver 2) / 가장 긴 감소 수열 찾기

🔎 BOJ 18353. 병사 배치하기 (Silver 2)

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

18353번: 병사 배치하기

 

💡 SOL

import sys
from bisect import bisect_left
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
dp = [0]
for a in arr[::-1]:
    if dp[-1] < a:
        dp.append(a)
    else:
        dp[bisect_left(dp, a)] = a
print(N - (len(dp) - 1))

기존 수열을 유지할 수 있는 경우( = 증가하는 수열에서 내가 가장 큰 값인 경우)에는 dp.append(a)

아닌 경우에는 bisect_left 라이브러리를 사용하여 해당 index 자리를 나로 대체한다.

정렬을 해치지 않고, 수열의 크기에는 영향이 없게 작은 값으로 업데이트 하기때문에, 가장 긴 수열을 만들 수 있는 가능성이 커진다.

💭 TIL

from bisect import bisect_left, bisect_right

index = bisect_left(arr, num)

주의할 점은 bisect 라이브러리는 증가하는(=정렬된) 리스트를 기준으로 실행된다.

따라서 이 문제와 같이 감소하는 수열을 찾는 경우라면,

주어진 배열을 뒤에서부터 탐색하여(arr[::-1]) 증가하는 수열을 찾음으로써 감소하는 수열을 얻을 수 있다.