[백준] 1890번 - 점프 (파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프

-> www.acmicpc.net/problem/1890

1890번: 점프

 

오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다. 

 

 

 

소스 코드)

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
dp = [[-1] * n for _ in range(n)]

def dfs(x, y):
    #기저 사례
    if x == n - 1 and y == n - 1:
        return 1

    if dp[x][y] == -1:
        dp[x][y] = 0
        if 0 <= x + graph[x][y] < n:
            dp[x][y] += dfs(x + graph[x][y], y)
        if 0 <= y + graph[x][y] < n:
            dp[x][y] += dfs(x, y + graph[x][y])

    return dp[x][y]

print(dfs(0, 0))