[백준 18353] 병사 배치하기

문제

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

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

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

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

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

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

 

초기 접근

---

점화식을 어떻게 세워야할 지 오래 고민했었다

 

1. d[i] = 현재 병사번호 부터 내림차순으로 세울 때 병사의 수가 최대가 될 때의 병사 수

2. d[i] = 현재 병사번호가 마지막이고 내림차순으로 세울 때 병사의 수가 최대가 될 때의 병사 수

3. d[i] = max(d[data[i]보다 큰 수중에 가장 작은 수의 병사번호]+data[i], d[i-1])

 

1번은 생각해봤을때 말이 안되는 방법이었다. 현재부터 세우는데 효율적인 방법을 이미 알고있는 상태여야 한다? 말이 안된다.

 

2번은 해결 아이디어에 가장 근접했는데, DP문제에 대한 경험이 없어서인지 현재 병사번호가 마지막이라고 생각하면 무조건 뒤쪽에서부터 구해야 한다는 고정관념이 있었다.

 

3번은 저대로만 세워진다면 해결이 가능할 것 같아서 "d[data[i]보다 큰 수중에 가장 작은 수의 병사번호" 이 함수를 구현하려 했지만 n^2시간이 걸릴 것 같아서 답이 안될 것 같았다.

 

 

 

 

해결 아이디어

---

2번 아이디어를 활용해서 가장 긴 내림차순 부분수열을 이용하면 된다.

 

d[i] = i보다 작은 병사번호들 중에서 내림차순이 가능한 경우에서 1을 더한 것 이다.

 

각 d[i]는 결국 병사 i를 마지막으로 내림차순으로 세울때 가장 길이가 긴 경우의 수 이다.

 

점화식으로 표현하면

d[0]~d[n-1] 을 전부 답의 최소 길이인 1로 초기화 하고 (병사가 어떻게 주어지든 1명의 병사를 선택할 수 있기 때문에 최소 길이는 1이다)

d[i] = max(d[i], d[j]+1) if arr[i] < arr[j]                  // 0<= j < i

 

 

 

 

정답 코드

---

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

d = [1 for _ in range(n)]

max_value = 0
for i in range(1, n):
    for j in range(0, i):
        if data[i] < data[j]:
            d[i] = max(d[i], d[j]+1)
    if max_value < d[i]:
        max_value = d[i]
if n == 1:
    print(0)
else:
    print(n - max_value)