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

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

---

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

int main()
{
	vector<int> arr(1001);//전체수열을 담을 vector
	vector<int> dp(1001, 1);//부분수열의 최대 길이를 담을 vector 크기는 모두 1로 초기화
	stack<int> answer;//결과 부분수열을 출력할 스택
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}
	dp[1] = 1;//1개의 수열의 최대 길이는 1
	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (arr[j] < arr[i])
			{
				dp[i] = max(dp[j] + 1, dp[i]);//모든 dp값을 비교하며 최대값 저장
			}
		}
	}
	int result = 1;
	for (int i = 1; i <= N; i++)
	{
		result = max(result, dp[i]);//1부터 N까지 중 증가집합의 길이가 가장 긴 길이를 출력
	}
	cout << result<<'\n';
//===============================여기까진 11053=============================
	int longestIndex = 1;
	for (int i = 2; i <= N; i++)//가장 긴 부분수열의 최대값이 있는 인덱스를 받아온다
	{
		if (dp[i] == result)
			longestIndex = i;
	}
	answer.push(arr[longestIndex]);//stack에 먼저 부분수열의 최대값을 넣어줌
	while(result--)
	{
		for (int j = longestIndex - 1; j > 0; j--)//부분수열의 최대값 바로 앞부터 for문
		{
			if (arr[longestIndex] > arr[j])//앞 숫자보다 뒤 숫자가 크고
			{
				if (dp[j] + 1 == dp[longestIndex])//앞숫자의 최대 수열길이 +1 이 현재dp값과 같다면
				{
					answer.push(arr[j]);//그 인덱스의 값을 스택에 추가
					longestIndex = j;
					break;
				}
			}
		}
	}
	while (!answer.empty())
	{
		cout << answer.top()<<' ';
		answer.pop();
	}
}

---

11053문제에서 구한 최대 길이 값을 가진 dp의 인덱스가 곧 가장 긴 부분수열의 최대값 인덱스이다

그 인덱스 부터 앞으로 쭉 내려가면서 dp값에 영향을 주었던(dp[j]+1 == dp[i])이었던 값의 인덱스를 찾아서 스택에 추가해준다

 

---

https://mun-coding.tistory.com/65

백준 11053 c++ 가장 긴 증가하는 부분 수열