백준 2631번: 줄세우기

[문제 링크]

2631번: 줄세우기

---

변형된 LIS 문제였다. 겉으로 보기엔 LIS 문제가 아닌듯 보이지만 가장 길게 오름차순으로 서있는 아이들을 제외한 나머지 아이들을 옮겨주면 최소한의 이동으로 줄을 세울 수 있기 때문에 결과적으로 입력받은 배열의 LIS를 구한 뒤 전체 아이들 수에서 LIS를 뺀 값이 곧 정답이 된다.

---

#include <iostream>
using namespace std;

int N, arr[201], memo[201];

int max(int a, int b) { return a > b ? a : b; }

int LIS(int start)
{
	if (start == N) return 1;

	int& ret = memo[start];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = start + 1; i <= N; i++)
	{
		if (start == 0)
			ret = max(ret, LIS(i));
		else if (arr[start] < arr[i])
			ret = max(ret, LIS(i) + 1);
	}

	return ret;
}

int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	cout << N - LIS(0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 102 day