백준 - 가장 긴 증가하는 부분 수열 5 (14003) [C++]

이 문제는 이분 탐색을 이용한 LIS 알고리즘으로 풀었다.

 

전형적인 LIS 문제지만, 최대 배열의 크기가 100만이므로 이분 탐색을 사용해야 한다.

 

또한 단순히 길이를 출력하는 데서 그치지 않고, 직접 답을 내야하므로 record 배열을 따로 두었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[1000000];
int N;

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

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

	vector<int> lis;
	vector<int> record;
	for (int i = 0; i < N; i++) {
		int num = arr[i];

		if (lis.empty()) {
			lis.push_back(num);
			record.push_back(0);
		} else {
			if (lis.back() < num) {
				record.push_back(lis.size());
				lis.push_back(num);
			} else {
				int index = lower_bound(lis.begin(), lis.end(), num) - lis.begin();

				lis[index] = num;
				record.push_back(index);
			}
		}
	}

	vector<int> answer;
	int initIndex = lis.size() - 1;
	for (int i = N - 1; i >= 0; i--) {
		int index = record[i];

		if (index == initIndex) {
			answer.push_back(arr[i]);
			initIndex--;
		}
	}

	reverse(answer.begin(), answer.end());

	cout << answer.size() << '\n';
	for (int a : answer) {
		cout << a << " ";
	}
	cout << '\n';

	return 0;
}