[백준] 2631번 줄세우기

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

2631번: 줄세우기

LIS(Longest Increasing Sequence)를 구하고 N에서 LIS를 빼주면 된다.

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

int main() {
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<int> dp(n);
	dp[0] = 1;
	int lis = 0;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && v[j] < v[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > lis)
			lis = dp[i];
	}
	cout << n - lis;
	return 0;
}