합친 LIS (난이도: 하)

( 여기서 설명하는 알고리즘은 아래의 사이트에서 LIS를 먼저 선행 후 풀는 것을 추천합니다. )

최대 증가 부분 수열(난이도: 하) (tistory.com)

최대 증가 부분 수열(난이도: 하)

 

 

 

1. 문제 설명

(1) 두 개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로

합친 것을 합친 증가 부분 수열이라고 부른다.

* JLIS(Joined Longest Increasing Subsequence)라고 부르며, LIS를 합친 것으로 보면 된다. 

 

(2) 이때, 두 입력으로 주어진 정수 수열 A와 B가 있을 때, 각각의 LIS를 구한 후 합친 LIS 즉, JLIS를

찾는 프로그램을 작성하시오.

* 예를 들어, '1 2 4' 와 '3 4 7' 이 있다면 '1 2 3 4 7'이 되므로 값은 5가 된다.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 A와 B의 길이 N(1<=N)과 M(M<=100)

(3) 그 후 세 번째 줄에 N개의 정수로 A의 원소들

(4) 그 후 네 번째 줄에 M개의 정수로 B의 원소들

 

출력 조건

(1) 각 테이스 케이스의 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

 

 

 

 

3. 제약 조건

(1) 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

public class JLIS {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int N,M;
    private static int[] A, B;

    private static int[][] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101][101];

            st = new StringTokenizer(sc.readLine());
            N = Integer.parseInt(st.nextToken());
            A = new int[N];
            M =  Integer.parseInt(st.nextToken());
            B = new int[M];

            st = new StringTokenizer(sc.readLine());
            for(int j=0; j<N; j++) {
                A[j] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(sc.readLine());
            for(int j=0; j<M; j++) {
                B[j] = Integer.parseInt(st.nextToken());
            }
            sb.append(solve(-1, -1)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int indexA, int indexB) {
        // 캐시 확인
        if(cache[indexA+1][indexB+1] != 0) {
            System.out.println("cache hit!! "+(indexA+1)+":"+(indexB+1)+"="+cache[indexA+1][indexB+1]);
            return cache[indexA+1][indexB+1];
        }

        // 어떤 원소이든 재귀호출을 무조건 1번 이상
        // 수행하므로 ret값은 0으로 초기화 한다.
        int ret=0;

        // -1을 처음부터 넣어서 모두 비교를 할 수 있게 한다.
        // 그러기 위해서는 아래와 같은 초기값을 위한 long max가 필요하다.
        long a = (indexA==-1 ? -999:A[indexA]);
        long b = (indexB==-1 ? -999:B[indexB]);
        long max = Math.max(a, b);

        // 어떤 수열이 먼저와도 상관없다.
        // 여기서는 A수열 비교
        for(int nextA=indexA+1; nextA<N; nextA++) {
            if(max<A[nextA]) cache[indexA+1][indexB+1] = ret = Math.max(ret, solve(nextA, indexB)+1);
        }

        // 어떤 수열이 먼저와도 상관없다.
        // 여기서는 B수열 비교
        for(int nextB=indexB+1; nextB<M; nextB++) {
            if(max<B[nextB]) cache[indexA+1][indexB+1] = ret = Math.max(ret, solve(indexA, nextB)+1);
        }
        return ret;
    }
}

 

 

 

 

7. 점화식

* 이때 NEXT(indexA)와 NEXT(indexB)는 증가 부분 수열의 다음 위치에 올 수 있는 A와 B 원소의 인덱스