다이나믹 프로그래밍: 병사 배치하기

문제정의

• N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 있습니다.
• 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 즉, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야합니다.
• 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용합니다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶습니다.

• 예를 들어, N = 7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하겠습니다.
  
• 이때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며, 5명이 됩니다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법입니다.
  
• 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기위해서 열외시켜야하는 병사의 수를 출력하는 프로그램을 작성하세요.

입력조건

• 첫째 줄에 N이 주어집니다. (1 <= N <= 2000)
• 둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 주어집니다. 각 병사의 전투력은 10000000보다 작거나 같은 자연수입니다.

출력조건

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

입출력예시

# 입력
7
16 11 4 8 5 2 4

# 출력
2

내가짠코드

array = [15, 11, 4, 8, 5, 2, 4]

result = 0
cnt = 0
while True: # 열외시키면서 array 길이가 변하기 때문에 for loop 대신 while 문과 cnt로 대체함.
    if cnt == len(array)-1: # 현 시점 실제 array의 길이와 같아지면 종료 (cnt는 인덱스를 나타내므로 길이에서 1을 빼준값과 비교)
        break
    if array[cnt] < array[cnt+1]: # 현재 병사 전투력이 그 다음 병사 전투력보다 낮은경우(내림차순에 위배)
        array.pop(cnt) # 현재 병사 열외
        result += 1 # 열외 수 증가
    else:
        cnt += 1 # 열외하지 않는 경우 1 증가
print(result)

정답코드

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

# 순서를 뒤집어서 'Longest Decreasing Subsequence' 문제로 변환
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))

로직

• 이 문제의 기본 아이디어는 Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어입니다.
• 예를 들어 하나의 수열이 있다고 합니다. array = [4,2,5,8,4,11,15]
• 이 수열의 Longest Increasing Subsequence는 [4,5,8,11,15]입니다.
• 본 문제는 Longest decreasing Subsequence를 찾는 문제로 치환하여 정답을 도출합니다.

Longest Increasing Subsequence

• d[i]는 array[i] 값을 마지막 원소로 가지는 부분 수열의 최대 길이로 정의합니다.
• 점화식은 다음과 같습니다.
• i는 각각의 원소, j는 그 앞에있는 모든 원소를 가리킵니다.