[백준 / 12015] 가장 긴 증가하는 부분 수열 2 (LIS) (이분 탐색)

1. 문제

 

 

 

 

2. 접근 방법

https://kbw1101.tistory.com/27

[백준/10816] 숫자 카드 2 (이분 탐색)

위의 문제와 비슷하게, 이분 탐색을 응용한 알고리즘인

Lower Bound를 이용하여 푸는 문제이다.

 

여기에서 Lower Bound 의 의미는 다음과 같다.

"찾고자 하는 수 이상의 값이 처음으로 등장하는 위치"

 

 

그렇다면 문제를 푸는 소개하겠다.

우선 LIS을 담을 배열을 만들고, 가장 첫 번째 원소의 값은 입력 배열의 첫 번째 원소와 동일하게 설정한다.

그 후, 우리는 입력 배열의 처음부터 끝까지의 숫자에 대해서, 다음의 과정을 반복할 것이다.

 

(1) 만약 숫자가 LIS 배열의 끝에 있는 숫자보다 크다면, LIS 배열의 맨 뒤에 그 수를 삽입한다.

(2) 만약 숫자가 LIS 배열의 끝에 있는 숫자보다 크지 않다면,

    LIS 배열에서의 Lower Bound(숫자)를 구하고, 그 곳의 값을 숫자로 치환시킨다.

 

이 과정을 반복한 후에, LIS 배열의 사이즈를 구하면 LIS의 크기를 구할 수 있다.

 

 

3. 구현

#include <iostream>
#include <algorithm>

using namespace std;

int A[1000000], B[1000000];
int N;
int BSize = 1;

int my_lower_bound(int n)
{
	int f = 0, l = BSize - 1, m;

	for (;;)
	{
		if (f > l) break;
		m = (f + l) / 2;
		
		if (B[m] >= n) l = m - 1;
		else f = m + 1;
	}

	return f;
}

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

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> A[i];

	B[0] = A[0];
	for (int i = 1; i < N; i++)
	{
		if (B[BSize - 1] < A[i])
		{
			B[BSize] = A[i];
			BSize++;
		}
		else
		{
			int idx = my_lower_bound(A[i]);
			B[idx] = A[i];
		}
	}

	cout << BSize << '\n';

	return 0;
}