[알고스팟] 합친 LIS

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • JLIS
  • 2000ms
  • 65536kb
  • 4301
  • 974 (22%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

어떤 수열에서 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 의 길이를 출력합니다.

예제 입력

3
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30

예제 출력

5
6
5

어떻게 풀까?

위 문제도 이전에 풀었던 LIS와 유사하게 풀 수 있습니다! 다만, 배열이 2개로 증가한 것 뿐입니다.

위 문제도 마찬가지로 '최적 부분 문제'를 이용하여 구할 수 있습니다.

다음 그림을 보면서 확인해 봅시다!

예제 문제 3번을 이용해서 보도록 합시다!

위에서 처럼 0번 인덱스와 이어지는 최대 합친 부분 수열을 찾기 위해서는

두 배열에서 10보다 큰 위에서의 1번 인덱스에서의 최대 길이, 아래 배열에서의 1번 인덱스에서의 최대 길이를 더해주면 됩니다.

따라서, JLIS(indexA, indexB)를 

1 + max( JLIS(nextA, indexB), JLIS(indexA, nextB) ) 의 형태로 나타낼 수 있습니다!!

또한 위의 식에서 중복되는 부분을 해결하기 위해서 JLIS(indexA, indexB)를 메모이션을 통해 저장합니다.

왜냐하면, JLIS(indexA, indexB)는 입력값에 따라서 값이 변화하지 않기 때문입니다!

이는 앞에서의 내용이 어떻게 되었더라도 뒤의 값에는 영향을 주지 않기 때문에, 이전에 배웠던 '최적 부분 구조'에 해당합니다.

결과로는 1, 2, 10, 20, 30의 5가 되는 것 입니다!

코드

//합친 LIS
//알고스팟
//https://algospot.com/judge/problem/read/JLIS
#pragma once
#include<cstring>
#include<cstdio>
 
int rLen;
int res[201], n, m;
int arr[2][101] = { 0 };
int lis[102][102];
 
int max(int i1, int i2)
{
    return i1 > i2 ? i1 : i2;
}
 
int JLIS(int prev, int idx1, int idx2)
{
    int& ret = lis[idx1][idx2];
 
    if (ret != -1) return ret;
 
    int cnt = 1;
 
    for (int i = idx1; i <= n; i++)
    {
        if (arr[0][i] > prev)
        {
            cnt = max(cnt, 1 + JLIS(arr[0][i], i + 1, idx2));
        }
    }
 
    for (int i = idx2; i <= m; i++)
    {
        if (arr[1][i] > prev)
        {
            cnt = max(cnt, 1 + JLIS(arr[1][i], idx1, i + 1));
        }
    }
 
    return ret = cnt;
}
 
 
void init()
{
    scanf("%d %d\n", &n, &m);
    memset(lis, -1, sizeof(lis));
 
    for (int i = 1; i <= n; i++) scanf("%d \n", &arr[0][i]);
    for (int i = 1; i <= m; i++) scanf("%d \n", &arr[1][i]);
}  
 
int JLIS()
{
    int t;
    scanf("%d\n", &t);
    while (t--)
    {
        init();
        int res = 0;
        
        for (int i = 1; i <= n; i++)
        {
            res = max(res, JLIS(arr[0][i], i + 1, 1));
        }
 
        for (int i = 1; i <= m; i++)
        {
            res = max(res, JLIS(arr[1][i], 1, i + 1));
        }
 
        printf("%d\n", res);
    }
    return 0;
}