[DP] (2) 병사 배치하기

이코테 p.380 병사 배치하기

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

18353번: 병사 배치하기

문제 해설 & 소스코드

• dp[i] = i번째 원소를 마지막 원소로 갖는 부분 수열의 최대 길이
• i번째 원소의 앞에 i번째 원소보다 작은 값을 갖는 j번째 원소가 있다면 dp 테이블 갱신
  • i번째 원소의 앞에 i번째 원소보다 작은 값이 있게 하기 위해서 입력받은 리스트의 순서를 반대로 뒤집음

# 입력 받기
n = int(input())
array = list(map(int, input().split()))
array.reverse() # 순서를 반대로 뒤집기

# dp[i] = i번째 원소를 마지막 원소로 갖는 부분 수열의 최대 길이
dp = [1] * n

for i in range(1, n):
  for j in range(0, i):
    # i번째 원소의 앞에 i번째 원소보다 작은 j번째 원소가 있는 경우
    if array[j] < array[i]:
      dp[i] = max(dp[i], dp[j] + 1) # dp 테이블 갱신

# 열외시켜야 하는 최소 병사의 수 출력
print(n - max(dp))