2XN타일링 문제에서 정확도는 패스가 되는데 효율성에서 문제가 되서 질문드립니다.

저는 문제를 2,1로 n을 만드는 경우의 수라고 생각을 해서 다음과 같이 코드를 짰고,

저는 시간복잡도가 n의 길이와 비례한다고 생각했는데 효율성에서 통과를 못해서요.

def solution(n):
    q = n//2
    d = {0:1,1:1}
    for i in range(2,n+1):
        d[i] = i*d[i-1]
    answer = 0
    for i in range(q+1):
				t = n - i*2
        answer += d[t+i] // (d[i] * d[t] )
    return answer%1000000007

시간복잡도가 원인이 아니라 메모리 or 숫자 크기의 문제입니다.

이거 함수 빼시고 직접 n = 1000 넣어보시면 값이 보정이 안되어있어서 무지무지 큰 값 나옵니다.

→ memory error or 그 크기의 숫자를 처리하는 시간 때문에 시간초과

전체적인 시간복잡도는 n은 맞습니다.

n = 99 만 되어도 99! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000의 숫자가 필요합니다.

n= 60000인 경우 1! ~ 60000! 숫자가 필요합니다.