백준 2631번 줄 세우기 (C++)

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

2631번: 줄세우기

 

단순하게 dp로 접근하기 보다는, 한가지 아이디어가 필요하다.

 

바로 LIS (최장 부분 증가 수열)이다.

 

어린이들의 이동 횟수가 최소가 되기 위해서는, 움직이지 않을, 즉 기준이 되는 어린이들을 잡을 필요가 있다.

 

어린이들의 정렬은 오름차순으로 이루어진다.

 

따라서 무작위로 섞여있는 어린이들의 번호 가운데에서, 오름차순으로 정렬된 최장 부분 수열을 찾아야한다.

 

그 부분 수열은 그대로 두고, 나머지 어린이들을 움직여주면 되겠다.

 

따라서 LSI의 길이를 전체 어린이의 수에서 빼주면 된다.

 

LIS를 구하는 알고리즘을 숙지하도록 하자.

 

#include<iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

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

	int d[200];
	int Max = 0;
	for (int i = 0; i < n; i++) { //LIS(최장 부분 증가 수열)구하기
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && d[i] < d[j] + 1) {
				d[i]++;
			}
		}
		if (Max < d[i]) Max = d[i];
		
	}

	cout << n - Max << '\n';
	return 0;
}