[백준] 18353 병사 배치하기

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

18353번: 병사 배치하기

문제를 풀다가 못 풀겠어서 풀이를 봤다... 최장 길이 부분수열(LIS) 문제와 유사한 문제로 개념이 있어야 쉽게 풀리는 문제였다. 풀이는 생각보다 간단하여 금방 풀었다. 

 

최장 길이 부분수열 (LIS) 를 푸는데 2가지 방법이 있다. 

 

첫 번째, 시간 복잡도가 O(N제곱)으로 푸는 방법.

두 번째, 시간 복잡도가 O(NlogN)으로 푸는 방법. 

 

두 가지 모두 살펴보고자 한다.

 

 

첫 번째, 내가 이 문제를 풀었던 O(N제곱) 방법이다. 푸는데 가장 간단한? 방법이라 생각한다. DP를 이용하는 방법으로 

 

for (int i = 0; i < N; i++) {
		brr[i] = 1;
	}

	int max_num = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				brr[i] = max(brr[i], brr[j] + 1);
			}
		}
	}

코드에 한 부분을 떼어왔다.

 

주어진 배열에서 인덱스를 한 칸씩 늘려가면서 확인하는 방법이다. 만약에 값 중에 arr[i] < arr[k]인 것이 있을 경우, brr 를 업데이트하는 것이다. 즉 자신보다 이전에 있던 배열의 값이 클 경우만 +1을 해주는 것이다. 

 

이렇게 2중 배열문을 완성하면 최장 길이를 알 수 있다 .

 

 

두 번째, 이분탐색을 이용한 방법이다.

 

n의 크기가 클 경우 O(NlogN) 의 시간복잡도를 갖기 때문에 O(N제곱)인 위의 방식보다 훨씬 효과적이다.

이 방식은 두 개의 배열이 필요하다. 편의상 arr, lis 배열이라고 하자

 

arr배열이 lis 배열의 가장 마지막 원소와 비교했을 때

 

- 증가하는 부분 수열일 경우, LIS 배열의 가장 끝에 추가한다.

 

- 증가하는 부분 수열이 아닐 경우, LIS배열을 이분 탐색하여 들어갈 위치를 찾아 값을 대체한다.

        (Lower_bound 함수를 이용하여 편하게 구하자)

 

이 부분을 arr 배열의 끝의 원소에 도달할 때까지 반복하자

LIS 배열의 마지막 원소가 있는 인덱스가 가장 긴 부분 증가 수열의 길이가 된다.

 

(※여기서 중요한 점은 이 알고리즘이 끝난 후 lis 배열의 원소 개수가 최대 증가수열 값을 의미하는 것이지 그 배열 자체가 최대 증가수열을 말하지는 않는다!)

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int brr[20000];

int main() {
	int N;
	cin >> N;
	
	vector<int> arr;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	
	for (int i = 0; i < N; i++) {
		brr[i] = 1;
	}

	int max_num = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				brr[i] = max(brr[i], brr[j] + 1);
			}
		}
	}



	for (int i = 0; i < N; i++) {
		cout << brr[i];
		max_num = max(brr[i], max_num);
	}
	cout << N - max_num;
}