[백준] 12738 가장 긴 증가하는 부분 수열 3 - C++

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

---

간단한 O(n log n) LIS 문제이다.

이분탐색을 구현하지 않아도 c++의 lower_bound 함수로 딸깍이 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<long> v;
	vector<long> lis;
	for (int i = 0; i < n; i++) {
		long x;
		cin >> x;
		v.push_back(x);
	}
	lis.push_back(v[0]);
	for (int i = 0; i < n;i++) {
		if (lis.back() < v[i]) {
			lis.push_back(v[i]);
		}
		else {
			long idx = lower_bound(lis.begin(), lis.end(), v[i]) - lis.begin();
			lis[idx] = v[i];
		}
	}
	cout << lis.size();
	return 0;
}

 

설명하기에는 필력에 한계가 있어서

이 알고리즘을 이해하는데 도움이 되었던 블로그 글을 첨부하겠다

https://eatchangmyeong.github.io/2022/01/20/why-is-lis-algorithm-so-confusing.html

---