아래 문제를 Python 3 로 풀 때 시간 초과가 납니다.
[[problem:JUMPGAME]]

풀이방법: Memoization
풀이출처: 종만북(알고리즘문제해결전략)

코드 설명:

runmap:
1. 주어진 숫자를 읽어서 오른쪽 또는 아래로 움직였을때의 답안을 재귀함수로 확인합니다.
2. 읽은 값이 0이면 True를 리턴합니다.

변수설명:

mapcheck: False로 초기화 후, 답을 발견하면 True로 해당 위치의 값을 변경합니다.

mapinput: 인풋으로 주어진 지도를 저장합니다.

cmov: 움직일 칸수를 저장합니다.

질문:

파이썬이 느려서 시간초과가 나는것인가요?
또는, 제가 잘못풀고있어서 시간초과가 나는것인가요?

def runmap(mapinput,mapsize,mapcheck,x,y):

    if not (x >= 0 and x < mapsize and y >= 0 and y < mapsize):
        return False
    if mapinput[x][y] == 0:
        return True

    if mapcheck[x][y]:
        return mapcheck[x][y]

    cmov = mapinput[x][y]
    mapcheck[x][y] = runmap(mapinput,mapsize,mapcheck,x + cmov,y) or \
    runmap(mapinput,mapsize,mapcheck,x,y + cmov)

    return mapcheck[x][y]



import sys

k = 0
n = int(sys.stdin.readline())
while k < n:
    mapsize = int(sys.stdin.readline().split()[0])
    kk = 0
    mapinput = [[0]*mapsize]*mapsize
    while kk < mapsize:
        tmp = list(map(int,sys.stdin.readline().split()))
        mapinput[kk] = tmp
        kk = kk + 1
    mapcheck = [[False]*mapsize]*mapsize
    isanswer = runmap(mapinput,mapsize,mapcheck,0,0)
    if isanswer:
        print('YES')
    else:
        print('NO')
    k = k + 1