[종만북 문제] 합친 LIS (문제 ID : JLIS, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 점화식을 잘 세워보자.

---

[종만북 문제] 합친 LIS (문제 ID : JLIS, 난이도 : 하)

이것도 LIS 와 비슷한 로직을 적용하면 된다.

일단, jlis 함수를 다음과 같이 정의할 것이다.

jlis(indexA, indexB) = A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분수열의 최대 길이

 

순서를 딱히 지정하지는 않았으니 A[indexA] 와B[indexB] 중 작은 쪽이 앞에 온다고 가정하자. 그럼 점화식을 아래와 같이 세울 수 있다.

그럼 위의 점화식을 실제로 구현해 보자! 😊

 

#include <iostream>
#include "stdlib.h"
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

int N;
int M;
int A[100];
int B[100];
int cache[101][101];

// 입력이 32비트 부호 있는 정수의 모든 값을 가질 수 있으므로
// 인위적인 최소치는 64 비트여야 함
const long long NEGINF = numeric_limits<long long>::min();

// min(A[indexA], B[indexB]), max(A[indexA], B[indexB]) 로 시작하는
// 합친 증가 부분 수열의 최대 길이를 반환한다.
// 단 indexA == indexB == -1 혹은 A[indexA] != B[indexB] 라고 가정한다
int jlis(int indexA, int indexB)
{
	// 메모이제이션
	int& ret = cache[indexA + 1][indexB + 1];
	if (ret != -1)
		return ret;

	// A[indexA], B[indexB] 가 이미 존재하지만, 값이 같을 수도 있다.
	ret = 0;
	long long a = (indexA == -1 ? NEGINF : A[indexA]);
	long long b = (indexB == -1 ? NEGINF : B[indexB]);
	long long maxElement = max(a, b);

	// 다음 원소를 찾는다
	for (int nextA = indexA + 1; nextA < N; ++nextA)
		if (maxElement < A[nextA])
			ret = max(ret, jlis(nextA, indexB) + 1);
	for (int nextB = indexB + 1; nextB < M; ++nextB)
		if (maxElement < B[nextB])
			ret = max(ret, jlis(indexA, nextB) + 1);

	return ret;
}

void sol()
{
	cout << jlis(-1, -1) << endl;
}

void inputHandler()
{
	cin >> N;
	cin >> M;

	for (int i = 0; i < N; ++i)
		cin >> A[i];
	for (int i = 0; i < M; ++i)
		cin >> B[i];

	for (int i = 0; i <= N; ++i)
		for (int j = 0; j <= M; ++j)
			cache[i][j] = -1;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();
	
		sol();
	}

	return 0;
}