문제
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있다
병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다.
다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다.
그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶다
병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를
출력하는 프로그램을 작성하라
문제 예시
문제 풀이
이 문제의 경우 병사의 최대의 수가 원하고자 하는 답이다. 여러가지 방법이 생각이 난다. 먼저 병사 최대의 수와 최소의 수를 특정할 수 있기에 이분 탐색을 생각 했지만, 문제에서 가지는 전투력과 정렬되지 않은 배열 때문에 이진 탐색으로 하는 것은 복잡해 보인다. 그렇다면 집중해서 봐야할 부분은 순서대로 정렬 되는 최대의 길이이다.
가장 대표적인게 LIS 인데, 만약 arr = {4,2,5,8,4,11,15} 가 있다고 가정하면 이 수열에서의 LIS는 {4,5,8,11,15}이다. LIS 알고리즘을 연속된 수열의 부분 수열의 최대 길이를 구하는 알고리즘으로 착각했었다. 그래서 다시한번 정리를 하자면...🥲
LIS (최장 증가 부분 수열)
- 원소가 n 개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 증가하는 수열의 최장 길이를 찾는다.
- 예를 들어
arr = {4,2,5,8,4,11,15}일 경우lis = {4,5,8,11,15}로 이분 탐색과 DP를 사용한 방법이 있다!
자 이제 다시 문제로 돌아오면 하나만 바꾸면 된다. lis 를 도출 할때 증가 수열을 대상으로 하기 때문에 lis 함수를 감소로 바꾸는 방법과 수열 자체를 뒤집어서 lis 함수가 적용될 수 있는 형태로 만들어 주는 것이다. 뒤가 더 간단해 보이니 한번 뒤집은 후 lis를 찾으면 그게 답이다.
n = int(input())
arr = list(map(int,input().split()))
arr.reverse()
# 1 로 초기화 하는 이유는 적어도 자기 자신은 존재하기 때문.
dp = [1] * n
for i in range(1,n):
# dp[i] = i 를 마지막 원소로 가지는 부분 수열의 최대 길이
for j in range(0, i):
# 0~j까지의 dp를 살피며 arr[i]가 더 크면 dp[j] + 1
# + 1은 arr[i]를 포함해야 하기 때문임.
if arr[j] < arr[i]:
dp[i] = max(dp[i],dp[j] +1)
# max(dp) = lis.
print(n - max(dp)) 