백준 2352 반도체 설계

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

2352번: 반도체 설계

 

LIS 알고리즘 문제다. 밑의 알고리즘에서 이진탐색을 이용해서 idx 값을 구했기 때문에 탐색에 O(logN)이고

N개의 숫자에 대해 이 탐색을 실행하기 때문에 O(NlogN)이다. 

 

이 문제는 LIS를 구할 때 "어떤 수열이 LIS인가?"를 묻지 않았기 때문에 그냥 개수만 찾았다.

그러면 arr에 들어있는 수열은 실제 LIS와 다를 확률이 아주아주 높다.

 

추적을 할 때는 index 배열을 추가로 설정하면 된다.

/* 반도체 설계 */

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

vector<int> arr;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int temp; cin >> temp;
		if (arr.empty())
			arr.push_back(temp);
		else {
			int idx = lower_bound(arr.begin(), arr.end(), temp) - arr.begin();

			if (idx == arr.size()) {
				arr.push_back(temp);
			}
			else {
				arr[idx] = temp;
			}
		}
	}
	cout << arr.size();

	return 0;
}