[BOJ] Q18353 병사 배치하기

[BOJ] Q18353 병사 배치하기

Question

Language: Python

Difficulty: Silver 2

이 문제는 LIS(Longest Increasing Sequence)의 반대인 LDS 문제이다. 가장 긴 감소하는 수열을 찾으면 되는 문제이다.

LIS 알고리즘은 아래와 같이 구할 수 있다.

주어진 data가 아래와 같다면

datas=[10,10,20,30,10,20,30,20,40]
num=len(datas)

알고리즘은 아래와 같다. 현재항에 대해 이전항들을 비교하면서 만약 이전항에 비해 크다면 이는 증가하는 수열을 만족하여 기존에 가장 긴 증가하는 수열의 길이에서 하나를 추가하면 된다.

dp=[1] * num
for i in range(num):
  for j in range(i):
    if datas[j] < datas[i]:
      dp[i]=max(dp[j]+1,dp[i]) 
print(max(dp))

위와 같이 알고리즘은 하지만 O(n²)으로 조금 무겁다. 이를 개선하기 위해 bisect 모듈을 사용한다.

L=[datas[0]]
for i in range(1,num):
  if L[-1] < datas[i]:
    L.append(datas[i])
  else:
    index=bisect_left(L,datas[i])
    L[index]=datas[i]
print(len(L))

위와 같이, 증가하는 수열 L을 두어서, 만약 마지막 등록된 값보다 현재항이 더 큰 경우 삽입하고, 그렇지 않은 경우 수열 내 적합한 위치에 추가함으로써 LIS을 구한다.

해당 알고리즘은 Time Complexity는 O(nlogn)이다.

Solution

from bisect import bisect_left
num=int(input())
datas=list(map(int,input().split()))

datas.reverse()
sequence=[]
sequence.append(datas[0])
for i in range(1,num):
  if sequence[-1] < datas[i]:
    sequence.append(datas[i])
  else:
    index=bisect_left(sequence,datas[i])
    sequence[index]=datas[i]
print(num-len(sequence))