백준] 2631 - 줄세우기(KOI 2001)

시간 제한 : 1초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int n, max, arr[201] = { 0, }, dp[201] = { 0, };
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			if (arr[j] < arr[i])
				dp[i] = dp[i] < (dp[j] + 1) ? (dp[j] + 1) : dp[i];
	max = -1;
	for (int i = 1; i <= n; i++)
		max = max < dp[i] ? dp[i] : max;
	cout << n - max - 1;
}

Tip

LIS 문제로 문제의 크기 자체가 크지 않기 때문에 이분 탐색을 이용하지 않는 방식의 DP를 사용했다.

n-LIS인 이유는 해당 LIS에 끼워넣는 방식이 최소 이동을 보장하기 때문이다.