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

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

6
10 20 10 30 20 50

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

4

풀이

'가장 긴 증가하는 부분 수열 1' 문제와 똑같은 문제이지만 수의 범위가 다른 문제입니다.

 

1의 경우 수의 범위가 1,000까지 였으므로 다이나믹 프로그래밍 알고리즘만 사용해도 풀이가 가능했으나 2번 문제의 경우 수의 범위가 1,000,000까지 이기 때문에 똑같은 풀이로 제출할 경우 시간 초과가 발생합니다.

 

때문에 시간 복잡도를 줄이기 위해 이분 탐색을 활용한 풀이를 구현해야 했습니다.

 

우선 배열을 입력받은 뒤, 증가하는 부분 수열을 저장하기 위한 벡터를 따로 선언하여 벡터에 추가된 가장 최근 값과 배열의 값을 비교한 뒤 배열의 값이 더 클 경우 그대로 벡터에 푸쉬하였고 더 작을 경우 이분 탐색을 통해 현재까지 저장되어 있는 부분 수열의 원소들과 비교해가며 해당 숫자가 삽입될 적절한 Index를 찾아 저장해주었습니다.

 

여기서 저희가 선언한 벡터의 경우 위와 같은 과정을 통해 원소의 순서가 자연스럽게 오름차순이 되기 때문에 정렬이 되어 있어야 한다는 이분 탐색의 조건에 만족할 수 있습니다.

---

#include<iostream>
#include<vector>

#define MAX 1000000

using namespace std;

int n;
int arr[MAX];
vector<int> vec;

void input()
{
	cin >> n;

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

void binary_search(int num)
{
	int left = 0, right = vec.size() - 1;
	int index = MAX;

	while (left <= right) {
		int cen = (left + right) / 2;
		if (vec[cen] >= num) {
			if (index > cen)
				index = cen;
			right = cen - 1;
		}
		else 
			left = cen + 1;
	}

	vec[index] = num;
}

void solve()
{
	vec.push_back(arr[0]);

	for (int i = 1; i < n; ++i) {
		if (vec.back() < arr[i])
			vec.push_back(arr[i]);
		else
			binary_search(arr[i]);
	}

	cout << vec.size();
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	return 0;
}