[BOJ] 12015번 가장 긴 증가하는 부분 수열 2 (C++)

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

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

 

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

int n;
int arr[1000001];
vector<int> seq;

void binary_search(int num){
	int low = 0, high = seq.size() - 1, mid;
	int ret = 1000000007;
	while(low <= high){
		mid = (low + high) / 2;
		int midnum = seq[mid];
		if(midnum >= num){
			if(ret > mid) ret = mid;
			high = mid - 1;
		}else{
			low = mid + 1;
		}
	}
	seq[ret] = num;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> arr[i];
		
	seq.push_back(arr[0]);
	for(int i = 1; i < n; i++){
		if(seq.back() < arr[i]){
			seq.push_back(arr[i]);
		} else{
			binary_search(arr[i]);
		}
	}
	cout << seq.size();
	return 0;
}

 

11053번과 같은 문제이지만 입력 범위가 크다.  11053번 풀이와 같이 동적계획법을 활용하여 풀면 시간복잡도가 O(n^2)이기 때문에 시간초과가 발생한다. 

 

이 문제를 해결하기 위해 이분 탐색을 활용했다.

예를 들어 10, 20, 30, 25, 15, 60 이라는 배열이 주어진 경우

1. seq[0]에 10 저장

2. seq[0](= 10) < 20이므로, seq[1]에 20 저장

3. seq[1](= 20) < 30이므로, seq[2]에 30 저장

4. seq[2](= 30) > 25이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, seq[2]에 저장되어있는 30을 25로 치환

5. seq[3](= 25) > 15이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, seq[1]에 저장되어있는 20을 15로 치환

6. seq[3](= 25) < 60이므로, seq[4]에 60 저장

 

최종적인 seq의 크기가 가장 긴 증가하는 부분 수열 크기와 동일하게 된다.