합친 LIS(JLIS) [JAVA]

 

문제

문제 링크 : algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

문제 ID	시간 제한	메모리 제한	제출	맞은 사람	정답 비율
JLIS	2000ms	65536KB	7329	1784	24%

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

 

풀이

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

작은 쪽이 앞에 온다고 할때 증가 부분수열의 다음 숫자는 A[indexA+1] 이후 or B[index B+1]이후의 순열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나.

이때 A[nextA]가 다음숫자일때 합친 즈가부분수열의 최대 길이 = 1+JLIS(nextA, indexB)

JLIS(index A, index B) = max ( max(JLIS(index A, index B), JLIS(nextA,indexB)+1) , max( JLIS(index A, index B), JLIS(indexA,nextB) +1 ) )

이때 A[-1] = 최소, B[-1] = 최소 로 두고 항상 JLIS에 포함된다고 함 (마지막에 -2 해주기)

그렇게 해서 0부터 탐색 (0일때 원소 1개)

 

코드

public class Main {
  	public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    static Integer[][] subsets;
    static Integer[] a;
    static Integer[] b;
    
    public static void main(String[] args)throws Exception {
    	int c = Integer.parseInt(br.readLine());
    	for( ; c>0; c--) {
    		String stl[] = br.readLine().split(" ");
    		int ans = 0;
    		a = new Integer[Integer.parseInt(stl[0])];
    		b = new Integer[Integer.parseInt(stl[1])];
            //-1,-1 (부분수열을 둘다 안합칠때부터 시작하므로)
    		subsets = new Integer[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;
    			}
    		}
    		
    		stl = br.readLine().split(" ");
    		for(int i =0; i<a.length; i++) {
    			a[i] = Integer.parseInt(stl[i]);
    		}
    		stl = br.readLine().split(" ");
    		for(int i =0; i<b.length; i++) {
    			b[i] = Integer.parseInt(stl[i]);
    		}
            //실제 답에서 -2 빼주기
    		ans = getMax(-1,-1) - 2;
    		sb.append(ans).append("\n");
    	}
    	System.out.println(sb.toString());
    }
    
    public static int getMax(int ai, int bi) {
    	//만약 값이 있으면 리턴
    	if(subsets[ai+1][bi+1] != -1) return subsets[ai+1][bi+1];   	
        
    	//ai가 -1이면 long 최솟값, 아니면 a[ai]
    	long am  = (ai == -1 ? Long.MIN_VALUE : (long)a[ai]);
    	long bm  = (bi == -1 ? Long.MIN_VALUE : (long)b[bi]);
        
        //그중 최대 (걔가 앞에오니깐)
    	long maxnum = Math.max(am, bm);
        
        //am, bm이 존재 (-1 즉 둘중에 하나가 공집합이어도 일단은 최소값으로 넣었음) 하므로 2개는 있다고 생각.
    	int sum = 2;
        
    	for (int i = ai+1; i < a.length; i++) {
    		if(maxnum < a[i])
    			sum = Math.max(sum, getMax(i,bi)+1);
    	}
    	for (int i = bi+1; i < b.length; i++) {
    		if(maxnum < b[i])
    			sum = Math.max(sum, getMax(ai,i)+1);
    	}
    	subsets[ai+1][bi+1] = sum;   	
    	return sum;
    }
}

 

결과