백준 7570 : 줄 세우기

​https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

아이들을 번호순으로 오름차순 정렬시키는데 필요한 최소 이동 횟수를 구해야합니다.

아이들은 맨 앞 또는 맨 뒤로만 이동할 수 있고, 이미 세워진 아이들 중 일부는 이미 오름차순으로 정렬된 상태에 있습니다.

그러므로 주어진 번호에서 가장 긴 1씩 증가하는 연속된 부분 수열의 길이를 구해주면, 이 아이들은 이미 오름차순으로 정렬되어있으므로 그 순서를 유지해도 됩니다.

따라서, (전체 아이의 수 - 가장 긴 1씩 증가하는 연속된 부분 수열의 길이)번 만큼 아이들을 이동시켜주면 됩니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n, a, m = 0, dp[1000001] = { 0 };

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		dp[a] = dp[a - 1] + 1;
		m = max(m, dp[a]);
	}
	printf("%d", n - m);
}