[백준] 14003번: 가장 긴 증가하는 부분 수열 5 (c++)

 

문제

---

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

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

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

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

14003번: 가장 긴 증가하는 부분 수열 5

 

문제조건

---

• N (1 ≤ N ≤ 1,000,000)
• -1,000,000,000 ≤ Ai ≤ 1,000,000,000

 

풀이

---

12738번: 가장 긴 증가하는 부분 수열 3을 꼭 먼저 풀고 풀어야 하는 문제이다. 이 문제에서 LIS의 길이는 구할 수 있었지만 정확한 LIS(Longest Increasing Subsequence)를 구하지는 못했다. 예를 들어  A = { 10, 40, 50, 30 }에 대한 증가하는 배열 V를 구해보면 [10] -> [10, 40] -> [10, 40, 50] -> [10, 30, 50]으로 원하는 답인 [10, 40, 50]과 다른 답이 나오는 것을 확인 할 수 있었다. 

플레티넘 문제 답게 LIS 알고리즘과 dp를 함께 사용해야 정답을 구할 수 있었다. 위 예시에서 원하는 답이 나오지 않는 이유는 이미 답이 구해졌지만 계속해서 값을 확인하기 때문이다. 따라서 가장 마지막 값을 저장해 놓으면 이를 방지할 수 있다. dp배열에 V배열에서의 위치를 기록해 놓는다. 이후 dp배열을 마지막부터 돌며 가장 큰 값을 뽑아내면 구하고자 하는 LIS를 거꾸로 구할 수 있다.

예시

A = {10, 20, 10, 30, 20, 50} 

10	20	10	30	20	50
✅ 0	✅ 1	0	✅ 2	1	✅ 3

A = {10, 40, 50, 30}

10	40	50	30
✅ 0	✅ 1	✅ 2	1

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, cnt;
int arr[1000001], dp[1000001];
vector<int> v, ans;
 
int main()
{
	cin >> N;
 
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
 
	v.push_back(arr[1]);
 
	for (int i = 2; i <= N; i++)
	{
		if (v[cnt] < arr[i])
		{
			v.push_back(arr[i]);
			cnt++;
			dp[i] = cnt;
		}
		else
		{
			// 같거나 작은 위치를 lower_bound로 찾음
			int pos = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
			v[pos] = arr[i];
			dp[i] = pos;
		}
	}
 
 
	// 값 복원
	int LIS = cnt;
 
	for (int i = N; i >= 0; i--)
	{
		if (dp[i] == LIS)
		{
			ans.push_back(arr[i]);
			LIS--;
		}
	}
 
	int size = ans.size();
	cout << size << '\n';
	for (int i = 0; i < size; i++)
	{
		cout << ans.back() << " ";
		ans.pop_back();
	}
 
}