[C++] BOJ(백준) 2631 줄세우기

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

2631번: 줄세우기

 

dp문제다.

아이들을 옮기는데 다른 제한이 없으므로 이미 일부분 정렬되어 있는 아이들을 제외하고 움직이는 방법이 최선이다.

증가하는 가장 긴 부분수열을 구하고 전체 수열의 개수에서 부분 수열의 개수를 빼주면 된다.

 

배열을 순회하면서 해당 숫자를 기준으로 앞 쪽을 탐색한다.

앞 부분 숫자 중 해당 숫자보다 작은 숫자가 있다면 현재 dp배열의 값과 비교한다.

if (arr[i] > arr[j]) 
    dp[i] = max(dp[i], dp[j] + 1);

 

dp[i]의 값이 정해지면 res의 값을 갱신한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n, res;
int arr[200];
int dp[200];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

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

┗|｀O′|┛