[백준 C++] 12015 가장 긴 증가하는 부분 수열 2 - 이분탐색

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

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int Number;
	cin >> Number;
	LIS.emplace_back(Number);
	for (int i = 1; i < N; ++i)
	{
		cin >> Number;
		if (Number < LIS.back())
		{
			int Index = lower_bound(LIS.begin(), LIS.end(), Number) - LIS.begin();
			LIS[Index] = Number;
		}
		else if (Number > LIS.back())
		{
			LIS.emplace_back(Number);
		}
	}

	cout << LIS.size();
}

---

 

LIS(Longest Increasing Subsequence) - 최장 증가 수열의 개념에 대한 이해가 필요한 문제입니다.

lower_bound 함수(이분탐색)를 사용해서 LIS를 유지하기 위한 최적의 위치에 수를 삽입하는 방식으로 풀었습니다.

 

1. 수가 LIS의 마지막 원소보다 크다면 LIS에 푸시

2. 수가 LIS의 마지막 원소보다 작다면 LIS 내의 적절한 위치의 원소와 교체

3. 최종 LIS의 크기 출력

---

참고자료

[최장 증가 수열] LIS(Longest Increasing Subsequence)

알고리즘 - c++ lower_bound, upper_bound 활용하기