백준 2631 / C++

https://www.acmicpc.net/problem/2631

이 문제는 LIS 문제이다  그 이유는 이 문제의 경우 학생들을 원하는 위치이 넣을 수 있으므로 정렬되어 있지 않은 학생들을 정렬된 학생의 알맞은 위치에 넣으면 되는것이다 즉 전체 수에서 LIS만큼  뺴주면 되는 문제였다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200];
int dp[200] = { 0, };
int lis = 0;
int main() {
	int n,x,y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <i; j++) {
			if (arr[i] > arr[j]) {
				dp[i]=max(dp[i], dp[j] + 1);
				lis = max(lis, dp[i]);
			}
		}
	}
	cout << n-lis;
}