[ 백준 1818 ] 책정리 (Lower Bound)

문제

책정리 1818번

알고리즘 문제를 틈틈이 풀려고 노력하고 있지만 여전히 많이 부족한 것 같다 😅
스스로 풀지 못했기 때문에 Crocus님 블로그를 참고하여 풀었다.

풀이

이 문제는 LIS 알고리즘을 응용해서 풀 수 있는데, 이를 위해서는 Lower Bound를 사용해야 한다.

• Lower Bound: target이 있으면 target 반환, 없다면 target보다 큰 첫 번째 위치(이상)를 반환
• Upper Bound: target보다 큰 첫번째 위치(초과)를 반환.

예를 들어, 책들의 번호가 2 1 4 5 3 이라고 할 때

➔ 2 : 아무 값이 없으므로 첫 번째 값을 넣는다.
2
➔ 1 : Lower Bound에 의해 가장 마지막 위치가 반환된다. (target보다 크거나 같은 위치를 찾지 못했으므로)
1
➔ 4 : 1보다 크므로 바로 넣을 수 있다.
1 4
➔ 5 : 4보다 크므로 바로 넣을 수 있다.
1 4 5
➔ 3 : Lower Bound에 의해 3보다 크거나 같은 첫 번째 위치(1)을 반환된다.
1 3 5

Lower Bound에 의해 책을 끼워넣을 때마다 책을 옮겨야 하는 횟수를 더해주면 된다. 혹은, 책 번호가 오름차순으로 바로 들어갈 수 있을때만 LIS 배열의 길이가 늘어나기 때문에 전체 책의 개수 - LIS 배열의 길이를 구하면 마찬가지로 책을 옮겨야 하는 횟수를 구할 수 있다.

코드

#include <iostream>
using namespace std;

int N, books[200000], LIS[200000];

// LIS(Longest Increasing Subsequence)
// target이 찾는 구간에 없는 경우 가장 마지막 위치 
// 있는 경우에는 교체되어야 할 위치(크거나 같은 첫 번재 위치) 반환 
int lowerBound(int start, int end, int target) {
	while (start < end) {
		int mid = (start + end) / 2;

		//찾고자 하는 값보다 작으면 오른쪽 범위에서 탐색한다.
		if (LIS[mid] < target) {
			start = mid + 1;
		}
		else {
			end = mid;
		}
	}
	return end;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	int ans = 0;
	LIS[0] = books[0];

	for (int i = 1, j = 0; i < N; i++) {
		// 끼워넣어야 할 책의 번호가 가장 큰 경우, 그냥 넣어도 됨 
		if (LIS[j] < books[i]) {
			LIS[++j] = books[i];
		}

		// 교체되어야 할 위치 추출 
		else {
			int pos = lowerBound(0, j, books[i]);
			LIS[pos] = books[i];
			ans++; //교체 횟수 
		}
	}

	cout << ans << endl;
	return 0;

}

Lower Bound 함수를 직접 짤 수도 있지만, C++의 lower_bound 함수를 이용해도 된다
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

소스코드 출처
Crocus
참고 자료
cppreference
occidere