합친 LIS (JLIS)

문제정보

시간제한 : 2000ms
메모리 제한 : 65536kb

문제

어떤 수열에서 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

소스

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

/*
 * 알고리즘 문제해결전략 정답소스 C++ -> JAVA
 * 
 * 풀긴풀었는데, 이해가 잘 안감.
 * -1부터 하는것도 이해가 안가고, JLIS(i, j)로 2중포문을 돌면서 0부터 계산하면 답이 안나오는게 이해가 안됨...
 * 이거만 붙들고 있을순 없으니 일단 패스.
 * */
public class Jlis {

    public static int N, M;
    public static int arrN[];
    public static int arrM[];
    public static int cache[][];

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("D:\\sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for(int testCase=1; testCase<=T; testCase++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            arrN = new int[N];
            arrM = new int[M];
            cache = new int[N+1][M+1];

            // dp 초기화
            for(int i=0; i<=N; i++) {
                for(int j=0; j<=M; j++) {
                    cache[i][j] = -1;
                }
            }

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                arrN[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; i++){
                arrM[i] = Integer.parseInt(st.nextToken());
            }

            int result = 0;

            result =JLIS(-1,-1);

            bw.flush();
            bw.write(result-2 + "\n");

        }

        bw.close();

    }

    public static int JLIS(int indexN, int indexM) {
        // 메모이제이션
        if(cache[indexN+1][indexM+1] != -1) {
            return cache[indexN+1][indexM+1];
        }

        // A[indexA], B[indexB]가 이미 존재하므로 2개는 항상 있다.
        int ret = 2;
        long a = indexN == -1 ? Long.MIN_VALUE : arrN[indexN];
        long b = indexM == -1 ? Long.MIN_VALUE : arrM[indexM];
        long maxElement = Math.max(a, b);

        // 다음 원소를 찾는다.
        for(int nextN = indexN+1; nextN < N; nextN++) {
            if(maxElement < arrN[nextN]) {
                ret = Math.max(ret, JLIS(nextN, indexM) + 1);
            }
        }
        for(int nextM = indexM+1; nextM < M; nextM++) {
            if(maxElement < arrM[nextM]) {
                ret = Math.max(ret, JLIS(indexN, nextM) + 1);
            }
        }

        cache[indexN+1][indexM+1] = ret;

        return ret;

    }

}

회고

잘이해를 못한거 같다.
인덱스를 -1부터 시작해서 다 탐색을 하겠다는건 얼추 이해가 가는데,
그렇게 하지않고 2중 포문으로 0부터 다 탐색하니 답이 안나왔다.. 뭔가 찝찝하지만 일단 넘기려고한다.

추가 입력

12
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
3 3
1 9 4
3 4 7
1 1
100
100
5 5
2 7 7 7 1
5 9 3 6 3
5 5
3 4 5 7 2
6 4 8 9 1
1 2
4
4 7
1 1
1
1
3 5
1 1 1
2 2 2 2 2
5 5
3 4 5 7 2
6 4 8 9 1
2 3
-2147483648 -2147483648
-2147483648 -2147483648 -2147483648

추가 입력에 대한 출력

5
6
5
5
1
4
7
2
1
2
7
1

Lithium Flower