합친 LIS - DP

이미 비슷한 문제를 푼 적이 있다. LIS 문제를 풀어보았다. 비슷한 형태의 문제들은 비슷한 부분 문제 정의를 사용해 풀 수 있는 경우가 많다.

 

기존 LIS를 푸는 문제 f는 다음과 같았다.

• f(start_idx) : start_idx 위치의 수에서 시작하는 LIS 개수 리턴

합친 LIS를 푸는 문제 f의 정의를 다음과 같이 정의한다.

• f(indexA, indexB) : indexA와 indexB 위치의 수에서 시작하는 합친 LIS 개수 리턴

indexA와 indexB위치의 수에서 시작하므로 다음에 오는 수는 indexA, indexB 위치의 수들보다 더 커야한다. 따라서 아래의 점화식이 만족한다. nextA는 다음에 올 수 있는 A의 수들의 인덱스이며 nextB도 다음에 올 수 있는 B의 수들의 인덱스이다. 

• f(indexA, indexB) = max( max( f(nextA,indexB) + 1 ), max( f(indexA,nextB) + 1 ) )

점화식을 세웠다해도 구현이 살짝 복잡하다. LIS를 구할때 f(-1)은 -∞수에서 시작하는 LIS 개수를 리턴한다고 가정했던 것처럼 f(-1,-1)은  -∞수에서 시작하는 합친 LIS 개수를 리턴한다고 가정한다. 그러면 다음 부분 문제 f(nextA,-1)은  -∞, nextA 위치의 수를 시작하는 하는 합친 LIS 개수를 리턴할 것이고 f(-1,nextB)는 -∞, nextB 위치의 수에서 시작하는 합친 LIS 개수를 리턴할 것이다. f(-1,-1)은 다음 부분 문제가 리턴하는 가장 큰 합친 LIS 개수에 + 1을 리턴하면 된다. f(-1,-1)은 -∞수에서 시작하는 합친 LIS 개수를 리턴하므로 answer을 구할때 -1을 한다는 것에 주의하자.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int testCase = Integer.parseInt(br.readLine());

        for(int t=0; t<testCase; t++) {
            int n,m;
            st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            int[] A = new int[n];
            int[] B = new int[m];
            int[][] dp = new int[n+1][m+1];

            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<n; i++) A[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<m; i++) B[i] = Integer.parseInt(st.nextToken());

            for(int i=0; i<n + 1; i++)
                for(int j=0; j<m + 1; j++)
                    dp[i][j] = -1;

            int answer = 0;
            answer = f(-1,-1,A,B,dp) - 1;
            System.out.println(answer);
        }
    }

    static int f(int indexA, int indexB, int[] A, int[] B, int[][] dp) {
        if(dp[indexA + 1][indexB + 1] != -1) return dp[indexA + 1][indexB + 1];

        int answer = 1;
        long max_value;
        if(indexA == -1 && indexB == -1)
            max_value = (long)Integer.MIN_VALUE - 1;
        else if(indexA == -1)
            max_value = B[indexB];
        else if(indexB == -1)
            max_value = A[indexA];
        else
            max_value = Math.max(A[indexA], B[indexB]);

        for(int i=indexA+1; i<A.length; i++) {
            if(A[i] > max_value)
                answer = Math.max(answer, f(i,indexB,A,B,dp) + 1);
        }
        for(int i=indexB+1; i<B.length; i++) {
            if(B[i] > max_value)
                answer = Math.max(answer, f(indexA,i,A,B,dp) + 1);
        }
        dp[indexA + 1][indexB + 1] = answer;
        return answer;
    }
}