[백준 BOJ] 18353 - 병사 배치하기

처음에는 어떤 유형의 문제인지 감을 못잡아서 2번 실패를 했다.

 

병사는 자신의 위치를 유지해야 하므로 따로 정렬을 하면 안되고, 그 안에서 내림차순으로 가는 가장 긴 수열을 찾아야 한다. 즉 LIS 알고리즘을 사용하면 된다. 

 

이때, LIS는 최장증가부분수열이지만 이 문제는 숫자가 감소하는 길이가 가장 긴 것을 찾아야 하므로 최장감소부분수열을 찾으면 된다.

 

LIS는 이중 for-loop을 사용하여 시간복잡도가 O(n^2)인 방법과 이분탐색을 사용하여 시간복잡도가 O(nlogn)인 방법이 있다. 이 문제는 N이 최대 2000이므로, O(n^2)의 시간복잡도를 가진 방법을 사용해도 무리가 없다.

 

 

소스코드

#include<iostream>
#include<algorithm>
#define MAX 2000
using namespace std;
int n;
int soldier[MAX];
int dp[MAX];


// LIS 문제
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	cin >> n;

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

	int result = 0;

	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (soldier[i] < soldier[j] && dp[i] < dp[j] + 1) { // 내림차순이므로 뒤에 병사가 더 작아야 함
				dp[i] = dp[j] + 1;
			}
		}
		result = max(result, dp[i]);
	}
	cout << n - result;
}