백준|7570번|줄 세우기

문제 설명

1부터 n까지의 정렬되어 있지 않은 배열을 입력받고 배열의 어느 값을 뽑아서 맨 앞이나 맨 뒤로 옮기는 연산을 수행하여 배열을 정렬하려 할 때 최소 몇 번의 연산이 필요한지 구하는 문제입니다.

작동 순서

1. 숫자의 개수 N을 입력받습니다.
2. 정렬되어 있지 않은 배열을 입력받습니다.
3. LIS 알고리즘을 통해 원소들이 증가하는 구간의 최대길이를 구합니다.
4. 배열에서 최대 연속 증가 구간을 제외한 모든 숫자들을 앞 또는 뒤로 이동시키는 횟수가 배열을 정렬할 때 필요한 최소한의 연산횟수이므로 [배열 길이-최대 연속 증가 구간]의 길이를 출력합니다.

소스코드

import sys
N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

dp = [0 for i in range(N+1)]

for n in num:
    dp[n] = dp[n-1]+1

print(N-max(dp))