[백준/BOJ] 백준 2352번 : 반도체 설계

www.acmicpc.net/problem/2352

2352번: 반도체 설계

가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다

 

코드

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

int n;
vector<int> c_port;
vector<int> make_long;
vector<int>::iterator it;

//가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		c_port.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		it = lower_bound(make_long.begin(), make_long.end(), c_port[i]);

		if (it == make_long.end())
			make_long.push_back(c_port[i]);

		else
			*it = c_port[i];
	}

	cout << make_long.size();

	return 0;
}