[Algorithm] ➕합친 LIS

0. 문제

어떤 수열에서 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 의 길이를 출력합니다.

1. 아이디어

두 인덱스를 비교하며 큰 값을 저장한 후,
한 개의 인덱스부터 차례대로 커지면서 큰 숫자가 있으면 함수를 호출함

2. 핵심 풀이

1) 두 인덱스 비교하여 큰 값 저장

long am = (ai == -1 ? Long.MIN_VALUE : (long)a[ai]);
long bm = (bi == -1 ? Long.MIN_VALUE : (long)b[bi]);
		
long max = Math.max(am, bm);

2) max보다 크면 함수를 호출함

for(int i= ai+1; i<a.length; i++) {
			if(max < a[i])
				sum = Math.max(sum, getMax(i,bi)+1);
		}
		
		for(int i= bi+1; i<b.length; i++) {
			if(max < b[i])
				sum = Math.max(sum, getMax(ai,i)+1);
		}

3. 코드

import java.io.*;

public class DP_EX_5 {
	static int [][] subsets;
	static int[] a; 
	static int[] b;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int c = Integer.parseInt(br.readLine());
		int ans = 0;
		
		for(;c>0; c--) {
			String st[] = br.readLine().split(" ");
			a = new int[Integer.parseInt(st[0])];
			b = new int[Integer.parseInt(st[1])];
			
			subsets = new int[a.length+1][b.length+1];
	
			for(int i=0; i<a.length+1; i++) {
				for(int j=0; j<b.length+1; j++)
					subsets[i][j] = -1;			
			}
			
			st = br.readLine().split(" ");
			
			for(int i=0; i<a.length; i++)
				a[i] = Integer.parseInt(st[i]);
			
			st = br.readLine().split(" ");
			for(int i=0; i<b.length; i++)
				b[i] = Integer.parseInt(st[i]);
			
			ans = getMax(-1,-1)-2;

			System.out.println(ans);
		}
		
	}
	
	static int getMax(int ai, int bi) {
		if(subsets[ai+1][bi+1] != -1) return subsets[ai+1][bi+1];
		
		long am = (ai == -1 ? Long.MIN_VALUE : (long)a[ai]);
		long bm = (bi == -1 ? Long.MIN_VALUE : (long)b[bi]);
		
		long max = Math.max(am, bm);
		
		int sum = 2;
		
		for(int i= ai+1; i<a.length; i++) {
			if(max < a[i])
				sum = Math.max(sum, getMax(i,bi)+1);
		}
		
		for(int i= bi+1; i<b.length; i++) {
			if(max < b[i])
				sum = Math.max(sum, getMax(ai,i)+1);
		}
		
		subsets[ai+1][bi+1] = sum;
		return sum;
	}

}

5. 결과

으음.. 성공