[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++)

문제 링크: https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

1. 주의할 점

- 이분탐색을 사용하는 LIS에 대해 알고 있어야 한다.

- 가장 긴 증가하는 부분 수열 2와 풀이 방법은 같다. 다른점은 모든 변수를 Int가 아닌 Long Long으로 받아들인다.

풀이 방법: https://imnotabear.tistory.com/183

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

 

#include <iostream>
using namespace std;
long long arr[1000000], dp[1000000], idx = 0, num;

long long binary_search(long long val) {
	long long l = 0, r = idx, mid, result = idx;
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (dp[mid] >= val) {
			result = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return result;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++)
		cin >> arr[i];
	dp[0] = arr[0];
	for (int i = 1; i < num; i++) {
		if (dp[idx] < arr[i]) {
			dp[++idx] = arr[i];
		}
		else {
			long long v = binary_search(arr[i]);
			dp[v] = arr[i];
		}
	}
	cout << idx + 1;
	system("pause");
	return 0;
}