백준 1890 점프 - [dp]

import sys
input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().split())) for i in range(N)]
dp = [[-1 for j in range(N)] for i in range(N)]

def dfs(y, x):
    if y == N-1 and x == N-1 : return 1
    if dp[y][x] == -1:
        dp[y][x] = 0
        jump = arr[y][x]
        if y + jump < N: dp[y][x] += dfs(jump + y, x)
        if x + jump < N: dp[y][x] += dfs(y, jump + x)
    return dp[y][x]

print(dfs(0,0))

dp를 최대한 활용해서 시간초과가 안나게끔 하는것이 핵심이었던 문제

 

 

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

1890번: 점프