백준 #1890 점프

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1

for r in range(n):
    for c in range(n):
        if arr[r][c] and dp[r][c]:
            dr = [arr[r][c], 0]
            dc = [0, arr[r][c]]
            for k in range(2):
                nr, nc = r + dr[k], c + dc[k]
                if nr >= n or nc >= n:
                    continue
                dp[nr][nc] += dp[r][c]

print(dp[n-1][n-1])

풀이

오랜만에 풀어보는 dp몬제이다.

예전에 풀었던 비슷한 문제가 생각나서 처음에 dfs로 도전했는데 계속 메모리 초과가 나서 실패했다 ㅠ

그냥 이중 for문으로 dp를 채워 나가는 방식으로 풀었다!

메모리 초과가 왜 났을까잉 ㅠ