ALGOSPOT - JLIS

문제

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

풀이

이 문제를 완전 처음에.. 그러니까 동적계획법이 뭔지도 모르고 접했을때는 그냥 두 수열을 중복되는 수 없이 한 수열로 합친 다음에 합친 수열의 길이를 출력하게 했다. 놀랍게도 이 방식이 예제 입력에 대해서는 제대로 된 답을 출력해주기 때문에 코드를 제출했으나 당연히 WA를 받았다.

그리고 몇 일 전에 LIS 문제를 해결한 뒤 이 문제를 다시 접했는데 이 때는 LIS와 비슷하게 해결하면 될 줄 알았다. 두 수열의 LIS를 각각 구한뒤 각 수열의 길이를 출력하는 방법을 생각해보았으나 세 번째 예제인 $A=\{10, 20, 30\}, B=\{10, 20, 30, 1, 2\}$같은 경우에서는 A,B 수열 모두 $\{10, 20, 30\}$가 LIS이므로 6을 반환하지만 실제로는 $A=\{10, 20, 30\}, B=\{1, 2\}$인 5가 답이다.

LIS 문제는 한 개의 수열에 대한 인덱스 값을 인수로 받는 solve(int)를 작성했었는데 이 문제도 비슷하게 두개의 수열의 인덱스 값을 각각 받는 solve(int, int)를 작성하면 될 것 같았다. 문제를 해결하는 코드를 작성하면서 아래와 같은 부분에 대해 유의하며 작성했다.

• 모든 원소의 값은 signed integer 범위에 들어간다. 즉, 최소값은 INT_MIN이다.
• 한 수열의 원소를 아무것도 선택하지 않는 상태가 있을 수 있다.

위 부분을 생각하며 아래와 같은 코드를 작성했다. 처음에는 두 수열 모두 아무것도 시작하지 않은 상태(-1, -1)로 시작하며 재귀적으로 solve(Ai, Bi)를 호출하여 JLIS를 구하게 했다. 

#include <cstdio>
#include <cstring>
#include <climits>
int n,m,A[100],B[100],dp[101][101];
int max(int a, int b){return a>b?a:b;}
int solve(int Ai, int Bi){
	int &ret = dp[Ai+1][Bi+1];
	if(ret != -1) return ret;
	ret = 0;
	int pA, pB, pivot;
	pA = Ai == -1 ? INT_MIN : A[Ai];
	pB = Bi == -1 ? INT_MIN : B[Bi];
	pivot = max(pA,pB);
	for(int i=Ai+1;i<n;i++)
		if(pivot < A[i])
			ret = max(ret, solve(i,Bi)+1);
	for(int i=Bi+1;i<m;i++)
		if(pivot < B[i])
			ret = max(ret, solve(Ai,i)+1);
	return ret;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int i;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		memset(dp,-1,sizeof(int)*101*101);
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		for(i=0;i<m;i++)
			scanf("%d",&B[i]); 
		printf("%d\n",solve(-1,-1));
	}
}