백준 2352번: 반도체 설계

[문제 링크]

2352번: 반도체 설계

---

이 문제를 풀면서 LIS를 O(N^2)이 아닌 O(NlogN) 시간에 푸는 방법에 대해서 배우게 되었다.

핵심은 lower_bound를 사용하여 logN 시간에 LIS배열을 완성한다는 것이다.

---

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

int port[40000];

int Greedy(int n)
{
	int LIS[40000], size = 1;
	LIS[0] = port[0];
	for (int i = 1; i < n; i++)
	{
		if (LIS[size-1] < port[i])
		{
			LIS[size] = port[i];
			size++;
		}
		else
		{
			int idx = lower_bound(LIS, LIS + size, port[i]) - LIS;
			LIS[idx] = port[i];
		}
	}

	return size;
}

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

	for (int i = 0; i < n; i++)
		cin >> port[i];

	cout << Greedy(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 114 day