[C++ 백준알고리즘] 백준 12015: 가장 긴 증가하는 부분 수열 2

 

 

>>> 풀이 전략 <<<

• LIS 알고리즘을 활용하라는 제목..
• 수열의 크기가 1,000,000 이다.  =>  DP를 통한 LIS ( X ) , Binary Search를 통한 LIS ( O )
• 부분 수열의 길이만 구하면 되므로, 배열을 두개 생성 ( LIS 임시배열, 입력 값을 받는 LIST 배열 )

 

#include <iostream>

int list[1000001] = {};
int lis[1000001] = {};

int binary(int j, int i);

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);


	int n;
	std::cin >> n;

	for (int i{ 0 }; i < n; i++) {
		std::cin >> list[i];
	}

	int j = 1;
	int i = 0;
	lis[0] = list[0];

	while(j <= n) {
		if (lis[i] < list[j]) {
			lis[++i] = list[j];
		}
		else if(lis[i] > list[j]){
			lis[binary(j, i)] = list[j];
		}
		j++;
	}

	std::cout << i+1 << "\n";
}

int binary(int j, int i) {
	int s = 0;
	int e = i;
	int mid;
	while (s < e) {
		mid = (s + e) / 2;
		if (list[j] > lis[mid]) {
			s = mid+1;
		}
		else if (list[j] < lis[mid]) {
			e = mid;
		}
		else {
			return mid;
		}
	}

	return s;
}