[AlgoSpot] 합친 LIS

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
문제링크

문제 풀이

• 동적 계획법을 이용하여 풀이하였다.
• 기본 LIS에서 확장이 필요하다.
• max(indexA, indexB) : A[indexA], B[indexB]에서 시작하는 가장 긴 합친 증가 부분 수열 최대 길이라고 놓자.
• 이 때 아래와 같은 점화식이 성립하게 된다.

  nextA : indexA 보다 크고 A[indexA] < A[nextA] 를 만족하는 인덱스들
  nextB : indexB 보다 크고 B[indexB] < B[nextB] 를 만족하는 인덱스들
  

+) (0, 0) 부터 시작하게 되면 전체 케이스를 커버할 수 없으므로 꼭 (-1, -1)부터 시작해야한다.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, N, M, result;
    public static int[] A, B;
    public static int[][] max;

    public static int solve(int indA, int indB) {
        int ret = max[indA + 1][indB + 1];
        if (ret != 0) return ret;
        ret = 2;
        int a = (indA == -1)? Integer.MIN_VALUE : A[indA];
        int b = (indB == -1)? Integer.MIN_VALUE : B[indB];
        int maxValue = Math.max(a, b);
        for (int i = indA + 1; i < N; i++) {
            if (maxValue < A[i])
                ret = Math.max(ret, solve(i, indB) + 1);
        }
        for (int i = indB + 1; i < M; i++) {
            if (maxValue < B[i])
                ret = Math.max(ret, solve(indA, i) + 1);
        }
        if (ret > result) result = ret;
        return max[indA + 1][indB + 1] = ret;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        C = scanner.nextInt();
        for (int c = 0; c < C; c++) {
            result = -1;
            N = scanner.nextInt();
            M = scanner.nextInt();
            A = new int[N];
            B = new int[M];
            max = new int[N+1][M+1];
            for (int i = 0; i < N; i++)
                A[i] = scanner.nextInt();
            for (int i = 0; i < M; i++)
                B[i] = scanner.nextInt();
            solve(-1, -1);
            System.out.println(result - 2);
        }
    }
}