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

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

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

---

문제 풀이

 이전 문제와 다른 점은 input의 개수이다. 따라서 이 문제의 핵심은 시간 복잡도를 줄이는 것이다.

이전 문제에서는 i - 1 회의 반복횟수로 시간 복잡도가 O(N^2)가 된다. 하지만 백만개의 인풋에 대해서 1초라는 시간 내로 연산을 끝낼 수가 없어 다른 방법으로 시도해야 한다. 

이중 탐색문으로 lower bound를 찾는 방법을 이용하면 시간 복잡도가 O(N log N)이 된다. 

 

함수 binary는 이중 탐색을 기반으로 한 lower bound(최소의 idx)를 찾아 반환한다.

값을 비교해서 타켓보다 크면 배열 DP의 다음 인덱스에 값을 저장한다.

같거나 작다면  함수 binary로 lower bound를 찾아 맞는 위치에 값을 저장한다.

변수 idx는 배열 DP의 마지막 인덱스를 저장하는 변수이다. 출력 시에는 길이를 출력해야 하므로 +1 해준다.

느낀 점

 시간 복잡도의 중요성을 보이는 문제이다. 이전 다이나믹 프로그래밍에선 적은 범위로 문제가 없었지만 이렇게 많은 인풋에 대해서 어떻게 처리할 것인지 따져보는 문제였다. 사실 지금 코드가 다음 문제와 바로 연관되어서 요구하는 것 이상으로 많이 생각해본 것 같아서 뿌듯하다.

코드

#include <iostream>

using namespace std;

int n;
int arr[1000001], dp[1000001];

int binary(int left, int right, int key) {
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (dp[mid] >= key) right = mid - 1;
		else left = mid + 1;
	}
	return left;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	dp[0] = arr[0];
	int idx = 0;
	for (int i = 1; i < n;i++) {
		if (dp[idx] < arr[i]) dp[++idx] = arr[i];
		else {
			int lower_bound = binary(0, idx, arr[i]);
			dp[lower_bound] = arr[i];
		}
	}

	cout << idx + 1;
}