동적 계획법 - 5. 합친 LIS

문제 : 합친 LIS (난이도 : 下)

 

https://algospot.com/judge/problem/read/JLIS

 분석

A[index_A], B[index_B]에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수를 JLIS(index_A, index_B)라고 하자.

두 순서는 작은 쪽이 앞으로 온다고 가정하고 다음과 같은 점화식을 세울 수 있다.

 

JLIS(index_A, index_B) = max{ max JLIS(next_A, index_B) + 1, max JLIS(index_A, next_b) + 1 }

소스 코드를 보면 무슨 말인지 이해가 될 것이다.

 

 

 구현

최소치 구현 부분도 눈여겨 봐보자.

//32비트의 정수가 입력치이므로, 최소치는 64비트여야 한다.
const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100]; // A[-1] = B[-1] = -INF
int cache[101][101];
//합친 부분 수열의 최대 길이를 반환한다.
int JLIS(int index_A, int index_B)
{
	//memoization
	int& ret = cache[index_A + 1][index_B + 1];
	if (ret != -1) return ret;
	//index_A, index_B가 존재하면 최소 길이는 2이다.
	ret = 2;
	long long a = (index_A == -1 ? NEGINF : A[index_A]);
	long long b = (index_B == -1 ? NEGINF : B[index_B]);
	long long nextElement = max(a, b);
	//find next element (본문의 점화식 부분)
	for (int next_A = index_A + 1; next_A < n; next_A++)
	{
		if (nextElement < A[next_A])
		{
			ret = max(ret, JLIS(next_A, index_B) + 1);
		}
	}
	for (int next_B = index_B + 1; next_B < m; next_B++)
	{
		if (nextElement < B[next_B])
		{
			ret = max(ret, JLIS(index_A, next_B) + 1);
		}
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		cin >> n >> m;
		
		//input A, B
		for (int i = 0; i < n; i++)
		{
			cin >> A[i];
		}
		for (int i = 0; i < m; i++)
		{
			cin >> B[i];
		}

		int ans = JLIS(-1, -1) - 2;
		cout << ans << '\n';
	}
	return 0;
}