백준 - 가장 긴 증가하는 부분 수열 2 (12015) [C++]

이 문제는 이분 탐색을 이용한 LIS 문제이다.

 

수열의 최대 크기가 1,000,000이므로 O(N^2) 알고리즘으로는 시간 초과가 나고, O(N log N) 이하 알고리즘을 고안해야 한다.

수열에 대해 루프를 돌면서 벡터의 적절한 위치에 값을 넣는다고 생각하면 쉽다.

 

이 알고리즘은 워낙 유명해서 그냥 외우고 있었다. 그러나 아직도 왜 이게 답이 나오는 알고리즘인지는 잘 모르겠다.

만약에 {10, 20, 9, 30, 20, 50} 이라는 수열에 대해 LIS의 길이를 구하면 4가 나오는데, 아래의 코드로 출력해보면 9 20 30 50 이라는 전혀 맞지 않는 부분 수열이 나오게 된다. 근데 길이는 정답이 나온다.

 

백준 14003 문제가 이를 출력까지 하는 문제인데, 여기서 제대로 파봐야겠다.

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

#define MAX 1000000

int arr[MAX];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	vector<int> result;
	for (int i = 0; i < N; i++) {
		int present = arr[i];

		if (result.empty()) {
			result.push_back(present);
		} else {
			int back = result.back();

			if (back < present) {
				result.push_back(present);
			} else {
				int index = lower_bound(result.begin(), result.end(), present) - result.begin();
				
				result[index] = present;
			}
		}
	}

	int answer = result.size();
	cout << answer << '\n';

	return 0;
}