문제 풀이

N이 1,000,000이므로 O(n^2)이 아닌 O(nlogn)의 방법으로 풀어야 되는 문제이다.
LIS를 nlogn으로 푸는 방법은 lower_bound를 이용하면 간단하다.
원리는 가장 마지막 원소가 작으면 작을수록 같은 길이의 수열중에서도 LIS가 가장 길 수 있다는 원리로 예를들면
{1, 2, 3, 7, 5, 6} 에서 다섯번째 원소까지 탐색을 했을때,
{1, 2, 3, 7} 과 {1, 2, 3, 5} 모두 LIS 길이가 같다.
하지만 후자가 마지막 원소가 5기때문에 같은 LIS길이를 가질지라도 이 후 7로 끝나는 것보다 더 긴 LIS 길이를 가질 수 있다.
그러므로 LIS는 빈 배열 부터 시작해서 마지막 원소보다 현재 원소가 크다면 뒤에 push해주고 그게아니라면 lower_bound로 "찾고자 하는 값 이상이 처음 나타나는 위치"를 찾아내어 그 자리에 대체시켜주면 된다.

참고로 LIS 배열안에 있는 원소들은 실제 LIS 수열을 뜻하는게 아니므로 주의.

문제 링크

boj/12015

소스코드

PS/12015.cpp

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
#include<math.h>

using namespace std;

vector<int> v;
int arr[1000001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	v.push_back(arr[0]);
	for (int i = 1; i < N; i++)
	{
		if (v.back() < arr[i])
			v.push_back(arr[i]);
		else if (v.back() > arr[i])
		{
			auto idx = lower_bound(v.begin(), v.end(), arr[i]);
			*idx = arr[i];
		}
	}
	cout << v.size();
}