[백준] 14003번: 가장 긴 증가하는 부분 수열 5

📌 문제

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

📌 설명

이분탐색을 통해 LIS의 길이 및 LIS를 구하는 방법을 알아야 한다.

먼저 LIS의 길이를 구하기 위해 임의의 벡터 tmp를 선언한다. 입력받은 배열 각각에 대하여 tmp에 들어갈 곳을 이분 탐색을 통해 찾는다. 만약 찾을 수 없다면 tmp에 값을 삽입하고, 찾았다면 해당 위치의 tmp의 값을 v[i]로 대체한다. tmp의 길이가 곧 LIS의 길이이다. 단, tmp에 저장된 배열의 값들을 실제 LIS와 다를 수 있다.

따라서 실제 LIS를 따로 구해야 한다. v[i]가 tmp에 삽입된 위치를 저장하는 배열 lis_idx를 선언한다. lis_idx를 역추적하여 얻은 수열이 LIS이다.

📌 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> tmp; // LIS의 길이를 구하는 데 사용
int lis_idx[1000000];

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

	vector<int> v;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	for (int i = 0; i < n; i++) {
		int idx = lower_bound(tmp.begin(), tmp.end(), v[i]) - tmp.begin();

		if (idx == tmp.size()) {
			tmp.push_back(v[i]);
		}
		else {
			tmp[idx] = v[i];
		}

		lis_idx[i] = idx;
	}

	cout << tmp.size() << "\n";

	// LIS에 해당하는 수의 인덱스 역추적
	int cur = tmp.size() - 1;
	vector<int> rev_lis;
	for (int i = n - 1; i >= 0; i--) {
		if (lis_idx[i] == cur) {
			rev_lis.push_back(v[i]);
			cur--;
		}
	}

	for (int i = tmp.size() - 1; i >= 0; i--) {
		cout << rev_lis[i] << " ";
	}
}