[백준][C++][DP] 11053, 14002 가장 긴 증가하는 부분 수열

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

 

 

가장 긴 증가하는 부분 수열 문제는 LIS 문제라고 부른다. 

 

이 문제에서 주의해야할 점은 점화식에서 D[n]이 정답이 아닐 수도 있다는 것. 

 

이 문제를 풀기 위해서 점화식을 D[n] = '길이 n의 수열에서 n번째 요소가 포함된 부분수열의 최대 길이' 로 정의하였는데, 문제에서 요구하는 것은 '길이 n의 수열에서 부분수열의 최대 길이' 이기 때문에 1부터 n까지의 D[n]값을 모두 검사해줘야 한다. 

 

D[n]은 i<n인 i에 대해, A[i]<A[n]이라면 D[n]=D[i]+1 이며, 가능한 모든 i에 대한 최댓값을 구해야 한다.

 

 

#include <iostream>

int a[1001]; //수열에 저장된 값
int d[1001] = { 0, }; //n번째까지의 가장 긴 부분수열의 길이

int dp(int n)
{
	if (d[n] != 0) return d[n];

	d[n] = 1;
	int len;
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < a[n])
		{
			len = dp(i) + 1;
			if (len > d[n]) d[n] = len;
		}
	}
	return d[n];
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];
	int result = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (dp(i) > result) result = dp(i);
	}
	std::cout << result;
}

 

 

 

 

---

 

 

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

 

 

 

이 문제는 위의 문제와 유사하지만, 부분수열을 출력하는 부분이 추가되었다. 

처음 풀 때는 벡터를 사용해서 부분수열 자체를 저장하는 방식으로 풀었는데, 부분수열에서 이전 요소의 인덱스를 따로 저장하여 역추적하는 방법도 있다는 것을 알게 되어서 두가지 방법으로 풀어봤다.

 

 

#include <iostream>
#include <vector>

int a[1001]; 
std::vector<int> d[1001]; 

std::vector<int> dp(int n)
{
	if (d[n].size() != 0) return d[n];

	int len = 0;
	int idx = 0;
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < a[n])
		{
			if (len < dp(i).size() + 1)
			{
				len = dp(i).size() + 1;
				idx = i;
			}
		}
	}
	if (idx != 0) d[n] = d[idx];
	d[n].push_back(a[n]);
	return d[n];
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];
	int len = 0;
	int idx = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (dp(i).size() > len)
		{
			len = dp(i).size();
			idx = i;
		}
	}

	std::cout << len << "\n";
	for (int i = 0; i < len; ++i)
		std::cout << d[idx][i] << ' ';
}

 

 

 

역추적하는 방식, 역추적을 하기 위한 배열 v[n] 추가, 역추적 함수 back 추가

 

#include <iostream>

int a[1001];
int d[1001];
int v[1001];

int dp(int n)
{
	if (d[n] != 0) return d[n];

	d[n] = 1;
	v[n] = 0;
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < a[n])
		{
			if (d[n] < dp(i) + 1)
			{
				d[n] = dp(i) + 1;
				v[n] = i;
			}
		}
	}
	return d[n];
}

void back(int n)
{
	if (v[n] == 0)
	{
		std::cout << a[n] << ' ';
		return;
	}

	back(v[n]);

	std::cout << a[n] << ' ';
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];
	
	int len = 0;
	int idx;
	for (int i = 1; i <= n; ++i)
	{
		if (len < dp(i))
		{
			len = dp(i);
			idx = i;
		}
	}

	std::cout << len << "\n";
	back(idx);
}