백준 12015 : 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

LIS 문제다. N의 크기가 100만으로 O(N^2) 풀이는 시간 초과가 발생하니 O(NlogN)으로 해결하면 된다.

아래 문제와 거의 유사한 문제다.

https://unfunhy.tistory.com/112

백준 2352 : 반도체 설계

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
void solution() {
	int tmp, target;
	vector<int> ans;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (ans.empty() || ans.back() < tmp) ans.push_back(tmp);
		else {
			target = lower_bound(ans.begin(), ans.end(), tmp) - ans.begin();
			ans[target] = tmp;
		}
	}
	cout << ans.size();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 8292 kb

시간: 176 ms