[백준] [C++] 2631번 줄 세우기

lis문제

 

#include <iostream>
#include <vector>
using namespace std;
int dp[201];
int main() {
	vector<int> vec;
	int n, tmp;
	cin >> n;
	vec.push_back(0);
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		vec.push_back(tmp);
	}
	int top = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = 1; //최장길이
		for (int j = 1; j < i; j++) {
			if (vec[j] < vec[i]/*이전값들과 비교*/
				&& dp[i] < dp[j] + 1/*선택했을때 최장길이가 더 커지나?*/) {
				dp[i]++;
			}
		}
		if (top < dp[i])top = dp[i];
	}
	cout << n - top;
}