골드2 - 백준 12015 가장 긴 증가하는 부분 수열 2

백준 12015 가장 긴 증가하는 부분 수열 2

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

접근방법

이 문제는 다른 사람의 풀이법을 참고해서 풀었다.
이 문제와 비슷한 문제로 14003 가장 긴 증가하는 부분 수열5가 있는데, 그 문제는 이전에 세그먼트트리를 사용하여 풀었다. 같은 방법을 적용하면 풀 수 있는 문제지만, 다른 풀이법으로 풀어보았다.
배열에 수를 차례대로 입력받으며 만약 배열의 마지막 수보다 크면 뒤에 추가해주고, 작다면 입력받은 수보다 작은 수를 이진탐색을 이용해서 찾은 후 그 다음 위치의 수와 바꿔주었다. 이렇게 마지막 수까지 입력받았을 때, 배열의 크기를 구하면 가장 긴 부분수열의 길이를 구할 수 있다.

풀이

numbers라는 벡터를 선언하고 수를 차례차례 입력 받아서 벡터의 마지막 수와 비교해주었다. 만약 크다면 벡터의 마지막에 넣어주고 작다면 이분탐색을 이용하여 그 다음 위치에 수를 저장해주었다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> numbers;
int cnt = 0;

int b_search(int num)
{
	int left = 0;
	int right = numbers.size();

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (numbers[mid] < num)
			left = mid + 1;
		else
			right = mid - 1;
	}

	return right + 1;
}

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++)
	{
		int num;
		cin >> num;

		if (numbers.empty() || num > numbers.back())
		{
			numbers.push_back(num);
			cnt++;
			continue;
		}
		
		numbers[b_search(num)] = num;
	}

	cout << numbers.size() << endl;
	return 0;
}