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

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

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)

출력

---

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

 

문제 풀이

---

dp 웰노운 문제.

수열의 크기가 최대 1,000,000이므로 O(n^2)으로는 풀리지 않는다.

vector를 이용해 각 길이의 맨 마지막 수에서 얻을 수 있는 가장 작은 수를 저장하는 방식으로 O(n log n)에 풀 수 있다.

예를 들어 10 20 10 30 20 50이라면

처음에는 벡터의 첫번째 칸에는 첫번째 수인 10이 저장된다. 이는 길이 1짜리 부분 수열의 맨 마지막 수에 올 수 있는 수 중 가장 작은 수가 10이라는 소리이다.

vector	index	0
	값	10

i=1일 때에는 값이 20이므로 길이 1짜리 부분 수열의 맨 마지막 수인 10에 이어 붙일 수 있다. 벡터에 20을 추가해준다. 이는 길이 2짜리 부분 수열의 맨 마지막 수에 올 수 있는 수 중 가장 작은 수가 20이라는 뜻이 된다.

vector	index	0	1
	값	10	20

i=2일 때 값이 10이므로 길이 1짜리를 만들 수 있다.

vector	index	0	1
	값	10	20

i=3일 때 값이 30이므로 길이 2짜리 부분 수열에 덧붙여 길이 3짜리를 만들 수 있다. 벡터에 30을 추가해준다.

vector	index	0	1	2
	값	10	20	30

 

i=4일 때 값이 20이므로 길이 1짜리 부분 수열에 덧붙여 길이 2를 만들 수 있다.

vector	index	0	1	2
	값	10	20	30

 

i=5일 때 값이 50이므로 길이 2짜리 부분 수열에 덧붙여 길이 4짜리를 만들 수 있다. 벡터에 50을 추가해준다.

vector	index	0	1	2	3
	값	10	20	30	50

따라서 만들 수 있는 가장 긴 증가하는 부분 수열의 길이는 4가 된다.

 

반복문을 도는 중 현재의 값을 어디에 덧붙일 수 있을지 찾는 것은 binary search를 이용해 찾는다.

 

만약 i=4일 때 값이 15였다면 길이 1짜리 부분 수열에 덧붙여서 길이 2짜리를 만들 때 가장 작은 수는 15가 된다. 따라서 벡터는 다음과 같이 업데이트가 되었을 것이다.

(i=4일 때 vector)

vector	index	0	1	2
	값	10	15	30

 

 

#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.at(dp.size()-1))
		{
			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;
}