알고리즘 문제해결전략 문제8.5 합친 LIS (ID: JLIS)

[문제 링크]

algospot.com :: JLIS

---

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

 

핵심은 두 개의 배열 A, B에서 현재 숫자보다 더 큰 수를 고르는 경우를 모두 해보면서 startA, startB를 초기값으로 시작할 때 가질 수 있는 최대 길이는 일정하기 때문에 이를 메모라이징하여 중복 탐색을 최소화 하는 것이라 생각한다.

---

#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits>
using namespace std;

int n, m, A[101], B[101], memo[101][101];
const long long MIN = numeric_limits<long long>::min();

int Solution(int startA, int startB)
{
	int& ret = memo[startA + 1][startB + 1];
	if (ret != -1) return ret;

	ret = 2;
	long long a = (startA == -1 ? MIN : A[startA]);
	long long b = (startB == -1 ? MIN : B[startB]);
	long long maxValue = max(a, b);

	for (int i = startA + 1; i < n; i++)
		if (maxValue < A[i])
			ret = max(ret, Solution(i, startB) + 1);
	for (int i = startB + 1; i < m; i++)
		if (maxValue < B[i])
			ret = max(ret, Solution(startA, i) + 1);

	return ret;
}
int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> A[i];
		for (int i = 0; i < m; i++)
			cin >> B[i];

		cout << Solution(-1, -1) - 2 << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 52 day