[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 증가하는 부분 수열[LIS] 4 (14002)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 증가하는 부분 수열 4 (14002)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 증가하는 부분 수열 4 (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<vector>
#include<algorithm>
using namespace std;

vector <int> A(1001); // 수열 A
vector <int> dp(1001); // 수열 A에서, 가장 긴 증가하는 부분 수열의 길이(개수)
vector <int> index(1001); // 인덱스값

void Index(int p) { // index값 출력 과정
	if (p == -1) { // -1을 만나면 반환하기 (첫번째 값)
		return; 
	}
	Index(index[p]); 
	cout << A[p] << ' ';
}


int main() {
	int N; // 수열 A의 크기
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	
	for (int i = 0; i < N; i++)
	{
		dp[i] = 1; // 배열 기본값 1로 설정 (기본적으로 하나만 값이 들어가도 1개이기 때문)
		index[i] = -1; // 인덱스 기본 값 -1로 설정
		for (int j = 0; j < i; j++)
		{
			if (A[i] > A[j] && dp[i] < dp[j]+1)
			{
				dp[i] = dp[j]+1;
				index[i] = j;
			}
		}
	}

	int ans = dp[0]; // 최대 길이를 구하기 위한 초기화
	int p = 0; // 마지막 inde값 저장을 위한 초기화
	for (int i = 0; i < N; i++)
	{
		if (ans < dp[i])
		{
			ans = dp[i]; // 최대길이 구하는 과정
			p = i; // 마지막 index값 저장을 위해
		}
	}
	cout << ans << '\n'; // 최대길이 출력

	Index(p); // index값 출력 과정

	return 0;
}