백준11568 - 민균이의 계락

 

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

11568번: 민균이의 계략

항상 두려워하던 LIS문제를 풀었다. 시간복잡도 O(n) = NlogN을 활용하였다. 주목할 점은 현재 숫자가 이전 수열 결과의 가장 큰 수 보다 클 경우 숫자를 넣어주고 그렇지 않은 경우는 현재 숫자보다 작으면서 제일 큰 숫자를 찾아 현재 숫자와 교체 해주는 것이다.

 

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

int main() {
	int n;
	int num;
	vector<int> v;

	cin >> n;
	v.push_back(0); //주어진 숫자보다 작은 숫자를 미리 넣는다.
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (v.back() < num) { //현재 숫자가 구한 수열의 가장 큰 수보다 큰 경우
			v.emplace_back(num);
		}
		else { //현재 숫자가 구한 수열의 가장 큰 수보다 작은 경우
			auto it = lower_bound(v.begin(), v.end(), num); //lower_bound로 이분탐색
			*it = num; //현재 숫자를 찾은 곳에 삽입
		}
	}

	cout << v.size() - 1;

}