[Baekjoon] 18353번 병사 배치하기

문제

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

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

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

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

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

입력

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

출력

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

예제

Example 1:

Input: 
7
15 11 4 8 5 2 4
Output: 
2

조건

시간 제한 : 1초

메모리 제한 : 256 MB

풀이과정

내 풀이

# n = 병사의 수
n = int(input())

# 전투력 입력
arr = list(map(int,input().split()))

# dp 테이블 선언
d = [1]*n

# 결과 계산 및 출력
for i in range(1, n):
    for j in range(i):
        if arr[j] > arr[i]:
            d[i] = max(d[i], d[j]+1)
print(n-max(d))

책 풀이

이 문제의 기본 아이디어는 ‘가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)’로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다. ‘가장 긴 증가하는 부분 수열’문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다.

예를 들어 하나의 수열 array = [10, 20, 10, 30, 20, 50]가 있다고 하자. 이때 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]이 될 것이다. $D[i] = array[i]$를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정의하면, 가장 긴 증가하는 부분 수열을 계산하는 점화식은 다음과 같다. 이때 초기의 DP 테이블의 값은 모두 1로 초기화한다. \(모든 \, 0\leq j < i \, 에\,대하여,\,D[i] = max(D[i],\, D[j]\,+\,1)\,\,\, if \; array[j] < array[i]\) 테이블이 갱신되는 과정을 그림으로 확인해보자. i를 1부터 n - 1까지 증가시키며, 점화식에 따라 테이블을 갱신했을 때의 결과는 다음과 같다.

	10	20	10	30	20	50
[초기 상태]	1	1	1	1	1	1
i = 1	1	2	1	1	1	1
i = 2	1	2	1	1	1	1
i = 3	1	2	1	3	1	1
i = 4	1	2	1	3	2	1
i = 5	1	2	1	3	2	4

최종적으로 테이블의 값은 [1, 2, 1, 3, 2, 4]이고, 이렇게 테이블에 남아 있는 값 중에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이이다. 즉, 현재 예시에서는 4가 최장 길이가 된다.

이제 우리가 풀어야 하는 문제를 확인해보자. 현재의 문제는 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치를 하고자 한다. 따라서 이 문제를 ‘가장 긴 감소하는 부분 수열’의 길이를 계산하는 문제로 간주하고, 입력으로 주어진 원소의 순서를 뒤집은 뒤에 ‘가장 긴 증가하는 부분 수열’문제를 풀 때의 점화식을 그대로 적용하면 해결할 수 있다.

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '가장 긴 증가하는 부분 수열' 문제로 반환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)
            
# 열외시켜야 하는 병사의 최소 수를 출력
print(n - max(dp))