(BOJ) 11053 가장 긴 증가하는 부분수열 - O(NlogN)방법 / lower_bound 구현

문제: https://www.acmicpc.net/problem/11053

 

문제풀이:

현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 

 

소스 코드:

시간복잡도: O($n^{2}$)

int n,arr[1001],dp[1001],res;

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


	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		res = max(res, dp[i]);
	}
	cout << res << '\n';

	return 0;
}

 

시간 복잡도: O(NlogN)

stl lower_bound 사용

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

int n, arr[1002], tmp[1002];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int sz = 1;
	tmp[0] = arr[0];
	for (int i = 1; i < n; i++) {
		int t = lower_bound(tmp, tmp + sz, arr[i])-tmp;
		if (t == sz) sz++;
		tmp[t] = arr[i];
	}
	cout << sz << '\n';

	return 0;
}

 

stl 미사용 - lower_bound() 구현

#include <iostream>
using namespace std;

int n, arr[1002], tmp[1002];

int func(int val, int sz) {  // lower_bound() 구현
	int l = 0, r = sz;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (tmp[mid] < val) l = mid + 1;
		else r = mid;
	}
	return r;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int sz = 1;
	tmp[0] = arr[0];
	for (int i = 1; i < n; i++) {
		int t = func(arr[i],sz);
		if (t == sz) sz++;
		tmp[t] = arr[i];
	}
	cout << sz << '\n';

	return 0;
}