백준 18353

병사 수(n)와 각 병사의 전투력(strengths)이 주어질 때,
최소한으로 병사를 열외시켜 남아있는 병사의 전투력이 내림차순이 되도록 해야 한다.

감소하는 가장 긴 부분 수열의 길이가 남아있는 최대 병사 수이므로,

strengths를 순서대로 탐색하면서..
1) 현재 strength(i)가 이전 병사의 strength(j)보다 크다면,
문제 조건을 충족하지 않기 때문에 고려하지 않아도 된다.

2) 현재 strength(i)가 이전 병사의 strength(j)보다 작다면,
문제의 조건을 충족하기 때문에 부분 수열의 길이를 업데이트해야 한다.

초기 세팅이 다음과 같을 때,

i == 2인 경우를 살펴보자.

1) j == 0인 경우
strength[i] == 4, strength[j] == 15이므로,
dp[i] == 1, dp[j] + 1 == 2의 값을 비교하면 dp[i] == 2로 업데이트 된다.

2) j == 1인 경우
strength[i] == 4, strength[j] == 11이므로,
dp[i] == 2, dp[j] + 1 == 3의 값을 비교하면 dp[i] == 3으로 업데이트 된다.

이 과정을 처음부터 끝까지 반복하면 최종적으로 아래와 같이 업데이트 될 것이다.

최종 코드는 아래와 같다.

# 18353

import sys

n = int(sys.stdin.readline())
strengths = list(map(int, sys.stdin.readline().split()))


dp = [1 for _ in range(n)]  # 감소하는 부분 수열의 길이
for i in range(1, n):
    for j in range(i):
        if strengths[i] < strengths[j]:
            dp[i] = max(dp[i], dp[j] + 1)

# 열외해야 하는 병사의 수 = 전체 병사의 수 - 가장 긴 부분 수열의 길이
print(n - max(dp))