[백준알고리즘] 1890번: 점프 -Python

[백준알고리즘] 1890번: 점프 -Python

https://www.acmicpc.net/problem/1890

1890번: 점프

재귀를 사용한 동적계획법으로 문제를 풀었다.

 

동적 계획법으로 풀 수 있는 문제이다 보니 여러 방법이 있겠지만 마지막에 도착할 수 있는 곳들의 경로의 수를 구해갔다.

 

중간에 메모리초과가 났었는데, visited[i][j] < 0일 때 아직 방문하지 않은 지점이기 때문에 visited[i][j]를 구해주어야 했는데, visited[i][j] <= 0처럼 등호가 들어가 버려서 무한루프를 돌아서 발생한 문제였다.

 

from sys import setrecursionlimit
setrecursionlimit(10**9)

def dp(i, j):
    if visited[i][j] < 0:    
        visited[i][j] = 0
        d = table[i][j]
        if i+d < n:
            visited[i][j] += dp(i+d, j)
        if j+d < n:
            visited[i][j] += dp(i, j+d)
    return visited[i][j]

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * n for _ in range(n)]
visited[-1][-1] = 1
dp(0, 0)
print(visited[0][0])

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다