18353-백준-병사 배치하기

1. 문제 출처

https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

2. 풀이

내림차순으로 정렬되어 있는 부분 최장 길이의 부분 수열을 구하는 문제이다..이는 LIS를 구하는 알고리즘과 매우 유사하다..이제 코드를 보자..

n = int(input())

soldier_list = list(map(int,input().split()))
# LIS (최장 증가 부분 수열) 처럼 사용하기 위해 오름차순으로 변환 해준다.
soldier_list = soldier_list[::-1]
length = [0]*n
# LIS의 길이 를 구한다.
for k in range(n):
    length[k] = 1
    for i in range(0,k):
        if soldier_list[i] < soldier_list[k] :
            length[k] = max(length[k] , length[i]+1)
            
print(n - max(length))

 0 번째 index 부터 n까지 1씩 증가시키며 최대 길이의 오름차순 부분 수열의 길이를 구한 후 전체 길이에서 빼준다.