[python] algospot JLIS

문제

두 개의 정수 수열 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의 길이를 계산하는 프로그램을 작성하세요.

-> 문제 링크 : https://algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

 

문제풀이

언뜻 생각하기에 두 문자열에서 증가 부분 수열을 얻은 뒤 합친 증가 부분 수열이 최대가 되려면 

A와 B에서 최장 증가 부분 수열을 구한 뒤 둘을 합치면 될 것 같다.

하지만 [1, 2, 10, 11, 12], [10,11,12]가 있다면 두 수열에 있는 최장 부분 증가 수열은 둘다 [10,11,12]이지만 

두 수열의 부분 증가 수열 합이 최대가 되는 경우는 [1,2] + [10,11,12]이다.

 

한 수열의 최장 증가 부분 수열을 구하는 문제를 조금 확장시키면 금방 해결할 수 있다.

수열이 A로 한 개 있을 때는 문제를 인덱스 i에서의 최대 부분 증가 수열의 합을  A[i]  + LIS(j) (단, j>i and A[j] > A[i] ) 와 같이 나타낼 수 있었다.

이를 두 수열로 확장시키면 수열 A를 가리키는 인덱스 i, 수열 B를 가리키는 인덱스 j가 있을 때

i,j 에서의 최대 부분 증가 수열의 합을 A[i] + B[j] + ( LIS(i,t) or LIS(k,j) ) ( 단, k와 i보다 크고 t는 j보다 크다. A[k]와 A[t]는 max(A[i], A[j])보다 크다. )와 같이 나타낼 수 있다.

 

시간복잡도는 메모이제이션으로 만들어지는 이차원 리스트의 크기인 O(MN) 

한 재귀 안에서 도는 두 개의 for문으로 발생하는 O(M+N)을 곱한 O(MN(M+N))이 된다

코드

import sys

# 1개
T = int(sys.stdin.readline().rstrip())

def JLIS(idx_a, idx_b) :
	
    if dp[idx_a][idx_b] :
        return dp[idx_a][idx_b]

    now_A = A[idx_a]
    now_B = B[idx_b]

    max_elem = max(now_A,now_B)

    ret = 2
    # 맨 마지막에 for문이 한번도 안돌아가는 경우를 생각해보자
    # (a,b) 뒤에 A[a], B[b]보다 큰 수가 없어서 쌓이는게 없다?  
    # 그러면 return 값은 최소 현재 두 인덱스에 해당하는 값 2개

    for i in range(idx_a+1, len_A) :
        if A[i] > max_elem :
            ret = max(ret,JLIS(i,idx_b)+1)

    for j in range(idx_b+1, len_B) :
        if B[j] > max_elem :
            ret = max(ret,JLIS(idx_a,j)+1)

    dp[idx_a][idx_b] = ret
    return dp[idx_a][idx_b]

for _ in range(T) :

    len_A, len_B = map(int, sys.stdin.readline().rstrip().split(" "))

    A = list(map(int,sys.stdin.readline().rstrip().split()))
    B = list(map(int,sys.stdin.readline().rstrip().split()))
    A.insert(0, -sys.maxsize+1)
    B.insert(0, -sys.maxsize+1)
    len_A += 1
    len_B += 1
    dp = [ [ None for _ in range(len_B)] for _ in range(len_A)]

    # [-9223372036854775806, 1, 2, 3]
    # [-9223372036854775806, 4, 5, 6]
    # A와 B 앞에 최소값이 들어가야 한다. 왜냐하면 JLIS는 첫 입력받은 두 인덱스에 해당하는 숫자를 포함하고
    # 그 포함한 문자열 두개를 기반으로 만들 수 있는 가장 큰 길이를 만든다.
    # JLIS에서 결과값이 A에서 두 숫자가 먼저 시작 할 수도 있다. [ A[0], A[4], B[2] ... ]  
    # 그렇다면 시작할 때 b_idx를 넣어줘야 하는데 방법이 없다
    # 그렇기에 첫 숫자를 가장 작은 수로 지정해놓고 시작하면 저 두 숫자를 포함한 리스트를 시작으로 원본 문자열 두개에서 최장 길이 문장을 찾아낸다.
    # 최소값 두개가 포함되어 있기에 결과에서 2를 뺴주면 된다.

    print(JLIS(0,0)-2)

 

초기 접근 방식과 오답의 원인

algospot에서 시간 초과가 나오는데 파이썬 문제인지 내 코드 문제인지 모르겠다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.