합친 LIS

풀이

두 수열에서 증가 부분 수열을 하나 고른 뒤 두 증가 부분 수열을 증가 부분 수열이 되도록 합쳤을 때 가장 길이가 긴 증가 수열의 길이를 구하는 문제입니다.

무식하게 풀기

딱 보고 드는 무식하게 푸는 방법은 이전 문제에서 봤듯이 한 수열의 증가 부분 수열은 시작 위치에 따라 결정됩니다. 이번 문제는 두 수열의 시작 위치가 인자로 주어집니다. int lis(int index) 함수가 int jlis(int indexA, int indexB) 함수로 바꾸면 됩니다. 두 수의 순서는 지정하지 않았으니, $A[indexA]$와 $B[indexB]$ 중 작은 쪽이 앞에 온다고 합시다. 그러면 이 증가 부분 수열의 다음 숫자는 $A[indexA + 1]$ 이후 혹은 $B[indexB + 1]$ 이후의 수열 중 $max(A[indexA], B[indexB])$보다 큰 수 중 하나가 됩니다. 그리고 $A[nextA]$를 다음 숫자로 선택했을 경우에 합친 증가 부분 수열의 최대 길이는 $1+jlis(nextA, indexB)$가 됩니다. 점화식으로 쓰면 다음과 같습니다.
$jlis(indexA, indexB)=max\begin{cases}max_{nextA\in NEXT(indexA)}jlis(nextA, indexB)+1\\max_{nextB\in NEXT(indexB)}jlis(indexA, nextB)+1\end{cases}$
이때 $NEXT(indexA)$와 $NEXT(indexB)$는 증가 부분 수열의 다음 위치에 올 수 있는 $A$와 $B$ 원소의 인덱스입니다.

비슷한 문제 이용하기

이전 최대 증가 부분 수열 문제에서 사용했던 알고리즘을 약간만 변형해서 구현하면 쉽게 해결할 수 있습니다.

시간 복잡도 분석

모든 부분 문제의 수는 $n\times m$이고 한 번 재귀 호출을 하면 $n + m$번 재귀 호출을 하기 때문에 $n$과 $m$의 최댓값인 100으로 가정해도 $10,000 \times 200 = 2,000,000$이므로 충분히 시간 안에 해결할 수 있습니다.

구현

import java.util.*;

public class Main {

    // 수열의 길이, 수열
    public static int n, m, A[], B[], cache[][];
    // 답
    public static int result = 0;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        m = scanner.nextInt();
        A = new int[n];
        B = new int[m];
        cache = 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();
        }
    }

    public static void solve() {
        result = jlis(-1, -1);
    }

    // min(A[indexA], B[indexB]), max(A[indexA], B[indexB])로 시작하는
    // 합친 증가 부분 수열의 최대 길이를 반환한다.
    // 단 indexA == indexB == -1 혹은 A[indexA] != B[indexB]라고 가정한다.
    public static int jlis(int indexA, int indexB) {
        // 메모이제이션
        if (cache[indexA + 1][indexB + 1] != 0) return cache[indexA + 1][indexB + 1];

        // A[indexA], B[indexB]가 이미 존재하므로 2개는 항상 있다.
        cache[indexA + 1][indexB + 1] = 2;
        long a = (indexA == -1 ? Long.MIN_VALUE : A[indexA]);
        long b = (indexB == -1 ? Long.MIN_VALUE : B[indexB]);
        long maxElement = Math.max(a, b);
        // 다음 원소를 찾는다.
        for (int nextA = indexA + 1; nextA < n; nextA++) {
            if (maxElement < A[nextA])
                cache[indexA + 1][indexB + 1] = Math.max(cache[indexA + 1][indexB + 1], jlis(nextA, indexB) + 1);
        }
        for (int nextB = indexB + 1; nextB < m; nextB++) {
            if (maxElement < B[nextB])
                cache[indexA + 1][indexB + 1] = Math.max(cache[indexA + 1][indexB + 1], jlis(indexA, nextB) + 1);
        }
        return cache[indexA + 1][indexB + 1];
    }

    public static void output() {
        System.out.println(result - 2);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

$indexA$와 $indexB$가 $-1$부터 시작하는 것에 유의해서 구현해야 합니다. 마지막 $result$에서 $-2$를 빼야 합니다. $A[-1], B[-1]$은 없는데도 있는 것처럼 간주해서 2를 더해줬기 때문입니다.

회고