acmicpc_12738(가장 긴 증가하는 부분 수열 3)(LIS)

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

int dp[1000001];
vector<int> v;
int x;

int main() {
	int n;

	cin >> n;
	v.push_back(-1000000001);

	for (int i = 0; i < n; ++i) {
		cin >> x;
		if (v.back() < x) {
			v.push_back(x);
		}
		else {
			auto it = lower_bound(v.begin(), v.end(), x);
			*it = x;
		}
	}

	cout << v.size() - 1;
}

기존의 LIS코드를 이용했는데 O(n^2)이 나오면서 시간초과가 나왔다.. 너무 뻔하다고 생각했는데 예상대로였다. 그래서 LIS에 대해서 더 알아보니 이분탐색 방법과 세그먼트 트리를 이용하는 방법이 있다고 한다. 그 중에서 이분탐색 방법을 이용해서 해결해 보았다.

기존의 O(n^2)알고리즘보다 더욱 간단해서 조금 놀랐다!

참고로, lower_bound(v.begin(), v.end(), x)는 vector v를 돌면서 x이상은 수의 위치를 찾는 함수이다!