JLIS 시간 초과가 나오는데 도와주세요

  • tagun11
    tagun11

    알고스팟 JLIS 문제

    링크: https://algospot.com/judge/problem/read/JLIS

    간략한 코드를 설명 드릴게요. 언어는 파이썬입니다. 푼 방법으로는 두 배열의 길이가 a,b라고 주어질 때 a X b인 2차원 배열을 만들어 각 위치일 때의 최대길이를 저장하고 그 값을 반환하는 방식으로 dp를 사용 하였습니다. 재귀 함수를 호출 시, 현재 배열 위치의 값과 첫 배열, 두번째 배열의 위치를 인자로 넘겨주어 그 현재 위치보다 뒤에 있고 값이 큰 것만 다시 재귀를 하는 방식으로 호출하였습니다. 최대한 많이 실행이 되면 (a * b) ^2보다 작다고 생각이 되는데 이 TLE가 나옵니다. 이보다 빠르게 할 수 없을까요?

    def jlis(cur, a_pos, b_pos):
        if cache[a_pos][b_pos] != -1: return cache[a_pos][b_pos]
        if num1[a_pos] == num2[b_pos]: ret =1
        else: ret =2
        for i in range(a_pos+1, a):
            if cur < num1[i]:
                ret = max(ret, jlis(num1[i], i, b_pos)+1)
        for i in range(b_pos+1, b):
            if cur < num2[i]:
                ret = max(ret, jlis(num2[i], a_pos, i)+1)
        cache[a_pos][b_pos] = ret
        return ret
    
    for _ in range(int(input())):
        a, b = map(int,input().split())
        num1 = list(map(int,input().split()))
        num2 = list(map(int,input().split()))
    
        cache = [[-1 for _ in range(b)] for _ in range(a)]
        ret = -1
        for i in range(a):
            ret = max(ret, jlis(num1[i],i,0))
        for j in range(b):
            ret = max(ret, jlis(num2[j],0,j))
        print(ret)
    

    4달 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.