[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++)

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

 

문제

---

수열 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,000,000,000 ≤ A_i ≤ 1,000,000,000)

 

출력

---

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

 

문제 풀이

---

N이 1,000,000까지이므로 각 인덱스 i마다 인덱스 0부터 i-1까지 탐색하는 O(n²)에 해결할 수 없다.

각 길이에 해당하는 가장 작은 숫자를 저장하는 벡터 dp를 만들어 이 문제를 해결한다. 예를 들어 인덱스 0은 길이 1로 얻을 수 있는 가장 작은 숫자, 인덱스 1은 길이 2로 얻을 수 있는 가장 작은 숫자... 등으로, LIS를 구하도록 구현하므로 해당 값들은 오름차순으로 값이 나타나며, 벡터의 크기가 이 문제의 답이 된다.

i가 0일 때에는 길이 1 짜리 가장 긴 증가하는 부분 수열을 얻을 수 있고, 벡터에 해당 값을 push한다. 각 인덱스를 탐색할 때 벡터의 마지막에 위치한 값보다 더 크다면 해당 부분 수열 뒤에 현재 인덱스의 값을 덧붙여 길이가 1 더 긴 부분 수열을 만들 수 있으므로 벡터에 해당 인덱스의 값을 push한다.

그렇지 않다면 dp 중 업데이트가 가능한 인덱스의 값을 업데이트한다. 예를 들어 dp 벡터에 10 20이 저장되어 있고 현재 탐색하는 인덱스의 값이 15라면 10 15로 숫자가 가장 작으면서도 증가하는 부분 수열을 만들 수 있다. dp 벡터의 인덱스 1은 15로 교체하도록 한다. 업데이트가 가능한 인덱스의 값은 lower_bound 함수를 사용하면 쉽게 구할 수 있다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	vector<int> dp;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	dp.push_back(arr[0]);
	for (int i = 1; i < N; i++)
	{
		if (arr[i] > dp.back())
		{
			dp.push_back(arr[i]);
		}
		else
		{
			int index = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
			dp.at(index) = arr[i];
		}
	}
	cout << dp.size() << "\n";
	return 0;
}