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

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

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

문제 풀이

이 문제의 핵심이라고 생각된 점은 가장 긴 증가하는 부분 수열의 "길이"를 출력한다는 점이다.

따라서 가장 긴 증가하는 부분 수열에 저장되는 배열을 꼭 정확할 필요가 없다.

따라서 LIS라는 배열을 만든 후 

배열의 마지막 값보다 크면 배열에 추가하고, 배열의 마지막 값보다 작은 경우 이분 탐색을 통해 숫자를 대치한다.

예를 들어

10 20 30 15 라는 숫자가 들어오면 우리는 10 20 30 이 가장 긴 증가하는 부분 수열임을 알 수 있다.

그러나 우리는 위의 규칙대로 코드를 실행하면

10

10 20

10 20 30

10 15 30 이 LIS 배열에 저장된다.

그러나 우리는 가장 긴 증가하는 수열의 길이만을 궁금하므로 길이가 3이 나오는게 중요하다!

 

소스 코드

#include <iostream>
using namespace std;

int LIS[1000001] = { 0 };
int num[1000001] = { 0 };

int idx_bsearch(int k, int index) {
	int lo = 0;
	int hi = index;

	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;

		if (LIS[mid] >= k)
			hi = mid;
		else lo = mid + 1;
	}

	return hi;
}


int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> num[i];
	}

	LIS[0] = num[0];

	int idx = 0;
	for (int i = 1; i < n; i++) {
		if (LIS[idx] >= num[i]) {
			int min_idx = idx_bsearch(num[i], idx);
			LIS[min_idx] = num[i];
		}
		else if (LIS[idx] < num[i]) {
			idx += 1;
			LIS[idx] = num[i];
		}
	}
    
	cout << idx + 1 << '\n';
}