<백준> 2631

줄세우기

문제

입력
첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력
첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

가장 긴 증가하는 부분 수열(LIS)를 응용한 문제이다. 옮겨지는 아이들은 연속되지 않는 위치의 아이들이기 때문에 전체 길이에서 가장 긴 길이를 빼면 움직여야 하는 아이들의 수를 구할 수 있다.

LIS의 점화식
dp[i] = max(dp[i], dp[j] + 1); 이걸 응용해서 풀면 된다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<int> v(n + 1);

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

	int result = 0;
	vector<int> dp(n + 1, 1);
	for (int i = 2; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j< i; j++)
		{
			if (v[i] > v[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		result = max(result, dp[i]);
	}
	cout << n - result;
}