백준 7570

백준 7570

이 문제는 번호가 주어진 학생들이 있을 때, 학생을 맨 앞이나 맨 뒤로 보냄으로써 번호순대로 만드는 최소의 값을 구하는 문제이다. 학생들의 번호들 중에 오른쪽으로 증가하는 방향이면서 연속되어 만들 수 있는 최댓값을 구해서 n에서 빼주면 답이 나온다.

n이 백만개이기 때문에 적어도 nlogn의 시간복잡도를 가져야하는데, 그러기 위해서 다이나믹 프로그래밍을 이용했다. dp[arr[i]]는 1번째 번호부터 i번째 번호까지 증가하면서 연속되어 만들 수 있는 값이다.

#include<bits/stdc++.h>
using namespace std;
int n; 
int dp[1000001];
int arr[1000001];
int mx;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		dp[arr[i]] = dp[arr[i] - 1] + 1;
	}
	sort(dp, dp + n);

	cout << n - dp[n - 1] << '\n';


}