✏️ 18353

문제

💡 문제 아이디어

• LIS (최장 증가 부분 수열) 을 구하는 문제이다

❓ LIS 이란

: 가장 긴 증가하는 부분 수열을 구하는 것
예를들어 4 2 1 3 5 8 6 7 이 있고 오름차순을 유지하면서 최대한 긴 수열을 만들어야 한다면
4 1 8 을 제거한
1(혹은 2) 3 5 6 7
이 될 수 있다

👀 풀이

# 18353

n = int(input())

arr = list(map(int, input().split()))

dp = [1 for _ in range(2000)]

for i in range(1, n) : # 첫 번째 원소 제외한 나머지 부터 검사 시작
    for j in range(i) : # 해당 i 번째 원소 전까지의 원소 하나씩 검사
        if arr[i] < arr[j] :
            dp[i] = max(dp[i] , dp[j]+1)

print(n-max(dp))

이때 dp[i] = max(dp[i] , dp[j]+1) 부분이 의미하는 것은 ,,,
dp 에서 i번째 까지 수열이 있을 때 가장 긴 수열의 길이, 즉 LIS 를 구하는 것이다.

따라서 답은 전체 길이 - LIS길이 가 되는 것이다