줄세우기 (feat. 백준, 2631번)

줄세우기
https://www.acmicpc.net/problem/2631

2631번: 줄세우기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2631
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, arr[201], dp[201] = { 0 };
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i], dp[i] = 1;
	for (register int i = 2, j; i <= N; ++i)
		for (j = 1; j < i; ++j)
			if (arr[j] < arr[i])		dp[i] = max(dp[i], dp[j] + 1);
	cout << N - *max_element(dp + 1, dp + 1 + N) << endl;
	return 0;
}
// *&)*@*

1. 문제에서 주어진 배열에서 이미 줄이 세워진 개수를 구합니다. 즉, 이미 줄이 세워진 아이들을 제외한 나머지 아이들만 움직인다면 해답이 되기 때문입니다.