백준 2631 : 줄세우기

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

2631번: 줄세우기

 

LIS(최장증가수열) 알고리즘으로 해결할 수 있는 문제다.

LIS 알고리즘으로 최장 증가수열의 크기를 구한 후 그 최장 증가수열에 포함되는 아이들을 고정시키고 나머지 아이들을 제 자리에 삽입하는 방법으로 정렬하면, 아이들을 최소한으로 움직여서 정렬시킬 수 있다.

 

LIS 구현에는 O(n^2) 방법과 이분탐색을 이용한 O(nlogn) 방법이 있는데 이 문제같은 경우는 입력값이 작아서 둘의 시간 차이가 없다.

하지만 동일한 목적을 가진 알고리즘이면서 더 적은 시간에 수행 가능하고, 결과값으로 최장 증가수열의 원소들 값까지 얻을 수 있는 O(nlogn) 풀이를 이용하는 것이 더 현명해보인다.

 

먼저 O(n^2) 풀이다.

#include <iostream>
#include <algorithm>

#define max(a,b) a>b?a:b
using namespace std;

int arr[200];
int dp[200];

int main() {
	int n; cin >> n;

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

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

	cout << n - *max_element(dp, dp +n);
	return 0;
}

 

다음으로 이분탐색을 이용한 O(nlogn)풀이다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[200];
int lis[200];

int main() {
	int n, idx = 0; cin >> n;

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

	lis[0] = arr[0];
	for (int i = 1; i < n; i++) {
    	//lis의 마지막 원소보다 arr[i]가 더 크다면
        //lis의 끝에 추가
		if (lis[idx] < arr[i]) {
			lis[++idx] = arr[i];
		}
        //그렇지 않다면,
        //이분탐색으로 찾아서 해당 위치의 값 갱신
		else {
			int target = lower_bound(lis, lis + idx, arr[i]) -lis;
			lis[target] = arr[i];
		}
	}

	cout << n - idx - 1;
	return 0;
}

메모리: 2024 kb

시간: 0 ms