JUMPGAME

  • jspark2
    jspark2

    아래 문제를 Python 3 로 풀 때 시간 초과가 납니다.
    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

    6년 전
0개의 댓글이 있습니다.

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