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

📌 문제

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

📌 설명

11053번: 가장 긴 증가하는 부분 수열 문제는 이중 for문을 돌며 현재 원소의 dp값은 현재 원소보다 작은 원소들의 dp값의 최댓값에 1을 더한 값이었다. 이번 문제는 위와 같은 O(N^2) 풀이로 풀게 되면 시간 초과가 발생한다. 

 LIS를 푸는 방법은 크게 두 가지가 있는데, DP를 활용한 방법과 이진 탐색을 활용한 방법이다. 이번에는 이진 탐색을 사용한다. 여러 LIS의 각 길이의 가장 작은 원소를 저장하는 배열을 선언한다. 이 배열을 arr로 하고 예를 들어보자면, arr[5] = 8은 여러 LIS 중 길이가 5인 원소 중 가장 작은 원소가 8이라는 뜻이다. LIS는 당연히 오름차순으로 정렬되어있으며, 이진 탐색을 사용할 수 있다. 즉, 전체 원소에 대하여 한 번 for문을 돌며 해당 원소보다 같거나 큰 첫 번째 원소를 해당 원소 값으로 바꾸면 된다. 만약 그러한 원소들이 없다면 배열에 삽입하면 된다.

📌 코드

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

using namespace std;

int dp[1000000];
vector<int> who; // dp[i]의 값 중 가장 작은 수 저장

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

	vector<int> v;
	for (int i = 0;i < n;i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	for (int i = 0;i < n;i++) {
		// 현재 원소가 LIS의 마지막 원소보다 더 큼
		int lower= lower_bound(who.begin(), who.end(), v[i]) - who.begin();

		if (lower == who.size()) {
			who.push_back(v[i]);
		}
		else {
			who[lower] = v[i];
		}
	}

	cout << who.size();
}