[ALGOSPOT] JLIS

algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

<문제>

어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

<입력>

입력의 첫 줄에는 테스트 케이스의 수 c ( 1 <= c <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 A 와 B 의 길이 n 과 m 이 주어집니다 (1 <= n,m <= 100). 다음 줄에는 n 개의 정수로 A 의 원소들이, 그 다음 줄에는 m 개의 정수로 B 의 원소들이 주어집니다. 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있습니다.

<출력>

각 테스트 케이스마다 한 줄에, JLIS 의 길이를 출력합니다.

 

<구현>

LIS와 같은 방법으로 구현

A배열과 B배열의 구분과 각각 인덱스 구별하여 LIS 구함.

 

 

 

다음은 책을 참고하여 작성한 소스코드입니다.

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n, m, A[101], B[101];
int cache[101][101];
 
int JLIS(int indexA, int indexB)
{
    int& ret = cache[indexA+1][indexB+1];
    if(ret != -1) return ret;
    ret = 2;
    lld a = (indexA == -1 ? LLONG_MIN : A[indexA]);
    lld b = (indexB == -1 ? LLONG_MIN : B[indexB]);
    
    lld mxe = max(a, b);
    for(int nextA = indexA+1; nextA<n ; nextA++)
        if(mxe<A[nextA]) ret = max(ret, JLIS(nextA, indexB)+1);
    for(int nextB = indexB+1; nextB<m ; nextB++)
        if(mxe<B[nextB]) ret = max(ret, JLIS(indexA, nextB)+1);
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>A[i];
        for(int j=0;j<m;j++)
            cin>>B[j];
        memset(cache, -1, sizeof(cache));
        cout<<JLIS(-1, -1)-2<<endl;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                cout<<cache[i][j]-2<<' ';
            cout<<endl;
        }
    }
    return 0;
}