[알고스팟/ALGOSPOT] 16. JLIS

알고라파덕~

이번 문제는 LIS를 2개를 이용하여 푸는 JLIS라는 문제입니다! 

이 문제 또한 동적계획법을 이용하여 해결을 하는데요~

동적 계획법이란 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다.

어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 c ( 1 <= c <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 A 와 B 의 길이 n 과 m 이 주어집니다 (1 <= n,m <= 100). 다음 줄에는 n 개의 정수로 A 의 원소들이, 그 다음 줄에는 m 개의 정수로 B 의 원소들이 주어집니다. 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있습니다.

출력

각 테스트 케이스마다 한 줄에, JLIS 의 길이를 출력합니다.

예제 입력

3
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30

예제 출력

5
6
5

문제 풀이법

이 문제는 그 전 문제 LIS의 확장판입니다! 이번에는 2개의 수열 중에서 수열의 값을 하나씩 선택해서 메모이제이션을 하는 방법입니다. 

점화식으로는

JLIS(indexA, indexB) = max{max(JLIS(nextA,indexB)+1), max(JLIS(indexA, nextB)+1)} 입니다.

#include <iostream>

using namespace std;
#include <algorithm>

const long long MINMIN = numeric_limits<long long>::min();
void INPUT();
int JLIS(int Aindex, int Bindex);
int A[110], B[110], C[110][110];
int N, M, ret, value;
int main()
{
	int testcase;
	scanf("%d", &testcase);
	while(testcase >= 1)
	{
		--testcase;
		INPUT();
	}
	return 0;
}
void INPUT()
{
	scanf("%d %d", &N, &M);
	for(int i=1; i<=N; i++) 
		scanf("%d", &A[i]);
	for(int i=1; i<=M; i++) 
		scanf("%d", &B[i]);
	
	for(int i=1; i<=N+1; i++)
		for(int j=1; j<=M+1; j++)
			C[i][j] = -1;


	printf("%d\n", JLIS(0, 0));
}
int JLIS(int Aindex, int Bindex)
{
	int &ret = C[Aindex+1][Bindex+1];

	if(ret != -1) return ret;
	
	ret = 0;
	long long a = (Aindex == 0 ?  MINMIN: A[Aindex]);
	long long b = (Bindex == 0 ? MINMIN : B[Bindex]);
	long long maxelement = max(a, b);
	
	for(int nexta = Aindex+1; nexta <= N; nexta++)
		if(A[nexta] > maxelement) 
			ret = max(ret, JLIS(nexta, Bindex)+1);

	for(int nextb = Bindex+1; nextb <= M; nextb++)
		if(B[nextb] > maxelement)
			ret = max(ret, JLIS(Aindex, nextb) +1);
	return ret;
}