(BOJ) 11722 가장 긴 감소하는 부분 수열 - O(NlogN) 구현

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

 

 

문제 풀이:

https://hororolol.tistory.com/103

(BOJ) 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;
}

 

풀이2 - 시간 복잡도: O(NlogN)

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

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

int func2(int val, int sz) {
	int l = 0, r = sz;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (tmp[mid] <= val) r = mid;
		else l = mid + 1;
	}
	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 = func2(arr[i],sz);
		if (t == sz) sz++;
		tmp[t] = arr[i];
	}
	cout << sz << '\n';

	return 0;
}