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

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

14002번: 가장 긴 증가하는 부분 수열 4

문제

---

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

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

 

입력

---

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

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

 

출력

---

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

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

문제 풀이

---

dp 문제.

i번째 배열의 값에 대해 처음부터 i-1번째 배열의 값을 탐색하면서(이 탐색 index를 j라 가정한다.) i번째 배열의 값보다 작으면서, j번째 배열의 값을 마지막으로 하는 부분 수열의 길이가 가장 긴 j를 찾는다.

이번 문제는 가장 긴 부분 수열 자체도 출력해야 하므로, 부분 수열에서 이전의 값을 가진 인덱스를 저장하는 배열을 추가로 넣는다.

 

예제 입력 1을 예시로 들어보자.

6
10 20 10 30 20 50

 

dp: 해당 값을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열

prev: 해당 값을 마지막으로 하는 가장 긴 증가하는 부분 수열에서 해당 값 이전의 인덱스를 저장하는 배열

(없을 경우 -1)

 

10은 첫번째이므로 길이를 1로 초기화한다.

배열의 값	10	20	10	30	20	50
dp	1
prev	-1	-1	-1	-1	-1	-1

---

20은 첫번째 값인 10 뒤에 붙일 수 있으므로 20으로 만들 수 있는 가장 긴 길이는 10으로 만들 수 있는 가장 긴 길이 1에 1을 더해 2가 된다. 또한 20 이전 값은 10이 되므로 10의 인덱스인 0을 저장한다.

배열의 값	10	20	10	30	20	50
dp	1	2
prev	-1	0	-1	-1	-1	-1

---

10은 인덱스 0부터 1까지 그 값 뒤에 붙일 수 있는 부분 수열이 없다.  따라서 dp[2]는 1이 된다.

배열의 값	10	20	10	30	20	50
dp	1	2	1
prev	-1	0	-1	-1	-1	-1

---

30은 10을 끝으로 하는 부분 배열 뒤에 붙일 수도 있고, 20을 끝으로 하는 부분 배열 뒤에 붙일 수도 있다. 20을 끝으로 하는 부분 배열이 더 기므로 dp[3]은 dp[1]+1인 3으로 채워지고, prev는 1를 저장한다.

배열의 값	10	20	10	30	20	50
dp	1	2	1	3
prev	-1	0	-1	1	-1	-1

---

20은 10을 끝으로 하는 부분 배열 뒤에 붙일 수 있다. dp[1]과 같다.

배열의 값	10	20	10	30	20	50
dp	1	2	1	3	2
prev	-1	0	-1	1	0	-1

---

50은 각각 10, 20, 30을 끝으로 하는 부분 배열 뒤에 붙일 수 있다. 그 중 30을 끝으로 했을 때 총 길이가 4가 되므로 dp[5]는 4로 채워지고, prev는 3이 된다.

배열의 값	10	20	10	30	20	50
dp	1	2	1	3	2	4
prev	-1	0	-1	1	0	3

 

이제 0부터 N-1까지 반복문을 돌면서 가장 긴 부분 수열의 길이를 찾아내고, prev의 값을 따라 이전의 값을 찾아 스택에 저장한 후 출력한다.

 

아래는 코드.

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

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

	int N;
	int maxLength;
	stack<int> s;
	cin >> N;
	int* arr = new int[N];
	int* dp = new int[N];
	int* prev = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		prev[i] = -1;
	}
	dp[0] = 1;
	for (int i = 1; i < N; i++)
	{
		maxLength = 0;
		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i] && dp[j] > maxLength)
			{
				maxLength = dp[j];
				prev[i] = j;
			}
		}
		dp[i] = maxLength + 1;
	}
	maxLength = 0;
	int maxIndex = -1;
	for (int i = 0; i < N; i++)
	{
		if (dp[i] > maxLength)
		{
			maxLength = dp[i];
			maxIndex = i;
		}
	}
	while (true)
	{
		s.push(arr[maxIndex]);
		maxIndex = prev[maxIndex];
		if (maxIndex == -1)
		{
			break;
		}
	}
	cout << s.size() << "\n";
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	return 0;
}