[백준] 2631번 - 줄세우기 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 줄세우기

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

2631번: 줄세우기

 

이미 정렬되어 있는 아이들 제외하고 정렬되지 않는 아이들을 옮긴다. 이때 옮겨지는 아이의 최소 수를 구해야 되므로 정렬되어 있는 아이들의 최대 수(Lis)를 구하여 전체 아이들의 수(n)에서 빼준다.

 

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 201
	#define MOD 100000
	using namespace std;
	typedef pair<int, int> p;
	int n, numbers[MAX];
	int cache[MAX];
	//Lis
	int solve(int idx) {
	int& ret = cache[idx + 1];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = idx + 1; i < n; ++i)
	if (idx == -1 || numbers[idx] < numbers[i])
	ret = max(ret, solve(i) + 1);
	return ret;
	}
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(cache, -1, sizeof(cache));
	cin >> n;
	for (int i = 0; i < n; ++i)
	cin >> numbers[i];
	cout << n - solve(-1) << endl;
	return 0;
	}

view raw 2631.cpp hosted with ❤ by GitHub