[14002] C++ : 가장 긴 증가하는 부분 수열 4

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

 

예제 입력 

6
10 20 10 30 20 50

예제 출력 

4
10 20 30 50

 

풀이

만약 이 문제에 대한 풀이 방법이 궁금해 들어온 사람이라면 아래 문제 풀이부터 보고 오길 바란다. 아래 문제에서 코드만 수정해 이 문제를 풀었기 때문에 중복 되는 설명은 생략할 예정이다.

2023.01.19 - [Computer Science/백준] - [11053] C++ : 가장 긴 증가하는 부분 수열

[11053] C++ : 가장 긴 증가하는 부분 수열

 

이전 문제와 동일한데 한 가지 차이나는 것은 해당하는 수열을 출력하는 것이다. 정말 고맙게도 해당하는 수열 중 아무거나 출력하면 되는 것이기 때문에 문제가 매우 간단해졌다. 

length를 대입할 때 그 length가 어디서 유래했는지 index를 적어주기만 하면 그 index를 따라가는 방법으로 수열을 추적할 수 있다.

1 5 2 8 4

length : 1 2 2 3 3
index  : 0 1 1 3 3

가장 긴 길이의 수열로 끝나는 것 중 8을 고르면, 8의 index는 3이니 그 앞 숫자는 2, 2의 index는 1이니 그 앞 숫자는 1, 1의 index는 0이니 수열의 끝이 된 것이다. 그래서 8 2 1 이 순서대로 나온다.

이때, 수열을 추적하는 방법이라 거꾸로 발견이 되기 때문에 stack을 이용해 반대로 뒤집어 주었다. 

for (int i = longest; i != 0;)
	{
		in.push(i);
		i = index[i];
	}

	while (!in.empty())
	{
		cout << arr[ in.top() ] << ' ';
		in.pop();
	}

 

최종 코드는 아래와 같다. 주의할 점은 지난번과 다르게 index를 기록해야하기 때문에 max 값을 기록하는 것이 아닌 maxindex를 기록하는 방법을 사용했다. ( max값은 arr[maxindex] 하면 나오니까...) 

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

int* length;
int* index;
int* arr;

int main()
{
	int n;
	cin >> n;
	stack<int> in;
	length = (int*)calloc(sizeof(int), (n + 1));
	index = (int*)calloc(sizeof(int), (n + 1));
	arr = (int*)calloc(sizeof(int), (n + 1));

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


	for (int i = 1; i <= n; i++)
	{
		int maxindex = 0;
		for (int j = 1; j < n; j++)
		{
			if (arr[i] > arr[j] && length[maxindex] < length[j])
				maxindex = j;
		}
		length[i] = length[maxindex] + 1;
		index[i] = maxindex;
	}

	int longest = 1;
	for (int i = 1; i <= n; i++)
	{
		if (length[i] > length[longest])
			longest = i;
	}

	for (int i = longest; i != 0;)
	{
		in.push(i);
		i = index[i];
	}

	cout << length[longest] << '\n';
	while (!in.empty())
	{
		cout << arr[ in.top() ] << ' ';
		in.pop();
	}
}