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

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

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4
10 20 30 50

 

 다이나믹 프로그래밍 문제이다. dp 배열에 저장할 원소는 해당 인덱스에서 최대 수열의 길이와 그 이전 인덱스이다. 여느 다이나믹 프로그래밍 문제와 마찬가지로 0 번 인덱스부터 N 번 인덱스까지 연쇄적으로 구한다. 풀이 방법은 다음과 ㅓ같다.

 

1. 입력 개수 N, 수열을 입력으로 받는다.
2. dp[MAX][2]를 만들고 dp[0][0], dp[0][1]에 각각 1, 0 을 채운다. dp[n][1] = n 으로 채운다.
3. dp를 연쇄적으로 채운다. 채우는 방법은 수열의 k 번째 인덱스에 대해 dp[k][0] 에 대해 dp[k-1][0] ~ dp[0][0] 중 가장 큰 값을, dp[k][1]에 대해서는 가장 클 때의 인덱스 값을 채운다.
4. 가장 긴 수열의 길이와 그 때의 수열을 출력한다. (이 부분은 코드를 참조하기를 바란다.)

 

코드는 다음과 같다.

 

#include <iostream>
#include <stack>

int array[1000];
int dp[1000][2];

int main()
{
	int N;
	std::cin >> N;

	for (int i = 0; i < N; i++) 
	{
		int data;
		std::cin >> data;
		array[i] = data;
		dp[i][1] = i;
	}

	dp[0][0] = 1;
	dp[0][1] = 0;

	if (N > 1) 
	{
		for (int i = 1; i < N; i++)
		{
			int max_seq = 0;

			for (int j = i-1; j >= 0; j--) 
			{
				if (array[i] > array[j]) 
				{
					if (max_seq < dp[j][0]) 
					{
						max_seq = dp[j][0];
						dp[i][1] = j;
					}
				}
			}

			dp[i][0] = ++max_seq;
		}
	}

	int index = 0;
	for (int i = 0; i < N; i++) 
	{
		if (dp[i][0] > dp[index][0]) 
		{
			index = i;
		}
	}

	std::cout << dp[index][0] << '\n';

	int i = index;
	std::stack<int> st;
	while (i != dp[i][1])
	{
		st.push(array[i]);
		i = dp[i][1];
	}

	st.push(array[i]);

	while (!st.empty()) 
	{
		std::cout << st.top() << ' ';
		st.pop();
	}

	return 0;
}

 

 생각할 게 조금은 많았던 문제이다. 케이스를 검사할 때, 오름차순, 내림차순, 원소가 1 개일 때를 고려해야 했었고, 그 과정에서 변수 초기화가 예상치 못한 문제를 줄여줄 수 있다는 것을 느낄 수 있었다. 또한 출력 역시 어떻게 해야 원하는 방식으로 출력할 수 있을 까를 미리 dp 배열을 채우는 과정에서부터 생각해야 되서 조금은 어려웠던 것 같다. 이것으로 글을 마친다.