[알고리즘 문제해결전략] JLIS - 합친 LIS

 

[생각의 흐름] - 오답

1. 수열A와 수열B의 LIS를 구해 더한다

-> 위와 같은 로직이면 예제 {10, 20, 30, 1, 2} {10, 20, 30} 일 때 정답은 {10, 20, 30}으로 JLIS의 길이는 3이됨 (정답은 5)

 

2. 수열A와 수열B의 중복 된 수를 한 쪽 수열에서 제거 한 뒤 각각 LIS를 구해 더한다.

-> 문제의 예제에서 정답은 나오나 코드 제출 시 오답나옴 -> 중복이 제거되어도 1과 같은 수열 케이스가 나오면 오답

 

[생각의 흐름] - 정답

1. 수열A와 수열B의 모든 수를 따지면서 LIS를 구한다.

-> "수열A의 수를 선택하거나 수열B의 수를 선택하거나"의 부분문제로 정의한다.

 

2. cache사용을 위해 계산의 중복이 있는지 찾아본다.

-> 예를들어 {1, 5, 9, 2} {3, 4, 8, 10} 인 경우 아래와 같이 중복되는 계산이 발생한다.

-> DP사용 가능

시작 -> 1선택 -> 5선택 -> 9 선택 ...

시작 -> 1선택 -> 4선택 -> 9 선택 ...

 

/* https://www.algospot.com/judge/problem/read/JLIS */
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <limits.h>

using namespace std;

const int MAX_SEQ = 111;

long long int A[MAX_SEQ];
long long int B[MAX_SEQ];
int cache[MAX_SEQ][MAX_SEQ];
int n, m;

int sol(int currentA, int currentB)
{
    int& ret = cache[currentA][currentB];
    if(ret != 0)
        return ret;

    long long int currentBigNum = A[currentA] > B[currentB] ? A[currentA] : B[currentB];

    // A에 있는 수 선택하는 경우
    for (int indexA = currentA + 1; indexA <= n; indexA++)
    {
        if(currentBigNum < A[indexA]) // 현재 가장 큰 수보다 큰 수를 선택
            ret = max(ret, sol(indexA, currentB) + 1);
    }

    // B에 있는 수 선택하는 경우
    for (int indexB = currentB + 1; indexB <= m; indexB++)
    {
        if(currentBigNum < B[indexB]) // 현재 가장 큰 수보다 큰 수를 선택
            ret = max(ret, sol(currentA, indexB) + 1);
    }

    return ret;
}

int main(void)
{
    int C;
    scanf("%d", &C);

    while (C--)
    {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &A[i]);
        }

        for (int i = 1; i <= m; i++)
        {
            scanf("%lld", &B[i]);
        }

        A[0] = B[0] = LONG_LONG_MIN; // sol(0,0)부터 시작하기 위해 long long int type중 가장 작은 값을 넣어준다.
        memset(cache, 0, sizeof(cache)); // cache를 0으로 초기화 하면 sol함수에서 귀찮은 예외처리를 제거할 수 있다.
        printf("%d\n", 
        sol(0, 0));
    }

    return 0;
}