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
    

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