18353번 - 병사 배치하기

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.

---

 이 문제를 들어가기 앞서, '가장 긴 증가하는 부분 수열 (LIS)'에 대한 개념을 알고가자. LIS란 주어진 숫자 배열의 부분 배열 중 오름차순으로 정렬 되어 있으면서 가장 길이가 긴 부분 수열을 찾는 문제를 말하는데, 대표적인 DP 문제 중 하나이다. 주어진 배열을 순회하면서, 0번째 인덱스부터 특정 시점의 인덱스까지의 원소들로 만들 수 있는 정렬된 부분 배열의 길이를 갱신 시켜주는 방식인데, 특정 시점까지의 부분 배열의 길이를 구하려면 어차피 이전 인덱스에서 구해놓은 길이가 필요하므로 DP로 접근된다는 것이다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

 위 그림과 같이, 예를 들면 i=3일 때 D[i]는 당연히 이전의 값이 20인 인덱스까지 만들 수 있는 LIS의 길이에 1만큼 더한 값이 될 것이고, 따라서 위와 같은 점화식이 성립하는 것이다.

 본 문제는 단지 LIS 문제에서 주어진 배열을 거꾸로 뒤집어 놓은 형태일 뿐 이므로, 코드는 다음과 같이 작성될 것이다.

코드

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

column.reverse()

dp = [1]*n

for i in range(1,n):
  for j in range(i):
    if column[j] < column[i]:
      dp[i] = max(dp[i],dp[j]+1)

print(n-max(dp))

 하지만 DP로 LIS문제를 접근하면, 코드에서 볼 수 있다시피 시간복잡도가 O(n^2)이다. 이 문제에서는 DP로 매우 충분하지만, DP 대신 이진 탐색으로 아예 LIS 리스트를 새로 만드는 방식을 이용하면 O(nlog(n))으로 시간복잡도가 어느정도 해소된다. 다음 링크에서 해당 내용을 다루고 있다.

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 | ChanBLOG (chanhuiseok.github.io)

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

코드

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

lis = []

column.reverse()

def binary_search(target,start,end):
  while start < end:
    mid = (start+end) // 2
    if lis[mid] < target:
      start = mid + 1
    else:
      end = mid
  return end

lis.append(column[0])
lis_length = 1

for i in range(1,n):
  if lis[-1] < column[i]:
    lis.append(column[i])
    lis_length += 1
  else:
    idx = binary_search(column[i],0,lis_length-1)
    lis[idx] = column[i]

print(n-lis_length)