[C++]BOJ 2352 - 반도체 설계

뭔가 했는데 알고리즘 분류를 보니 LIS라고 한다.

lower_bound로 최장증가수열을 구현하는 방식을 봤는데 실제로 유효한 수열을 구하진 않았다.

그런데 이 문제는 수열을 구하는 게 아니라 수열의 길이만 구하면 되므로 최대한 생략하고 수열의 길이만 구하도록 바꿨다.

#include <iostream>
using namespace std;
int n, g, t, L[40001];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> t;
		auto p = lower_bound(L+1, L+g+1, t);
		*p = t;
		if(p == L+g+1) g++;
	}
	cout << g;
}

나중에 더 찾아봐야 겠다.