백준 12015번 가장 긴 증가하는 부분 수열 2 C++풀이

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

12015번: 가장 긴 증가하는 부분 수열 2

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

최장 증가 부분 수열(LIS)를 구하는 문제이다.

{10, 20, 10, 30, 20, 50}의 LIS는 10과 20을 뺀  {10, 20, 30, 50}로, 길이는 4이다.

 

문제의 포인트

lower_bound를 활용할 수 있는가?

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, vn, cnt=0;
	vector<int> v;
	cin >> n;
	v.push_back(-1);
	for (int i = 0; i < n; i++)
	{
		cin >> vn;
		if (vn > v.back()) //증가 수열인 경우
		{
			v.push_back(vn);
			cnt++;
		}
		else
		{
			vector<int>::iterator low =
			lower_bound(v.begin(), v.end(), vn);
			*low = vn;
		}
	}
	cout<< cnt;
}

여담

lower_bound가 잘 기억 나지 않는다. 추가로 공부를 해보고 포스팅을 할 것이다.