BOJ 1890 점프

N*N 게임판에서 각 칸에 숫자가 적혀있고, 가장 왼쪽 위의 칸에서 가장 오른쪽 아래 칸으로 이동하는 경로의 수를 구하는 문제인데, 가장 왼쪽 위의 칸에서 시작해서 현재 있는 칸에 적힌 숫자만큼 오른쪽 또는 아래쪽으로만 이동할 수 있다.

일일이 다 해볼 경우 경우의 수가 매우 많으므로 중복되는 부분은 memoization을 통해 해결하도록 dp를 이용하자.

d[r][c] = (r, c)칸에서 출발해서 (n, n)칸(가장 오른쪽 아래 칸, 목적지)까지 가는 경로의 수.
d[r][c] = d[r+num[r][c]][c] + d[r][c+num[r][c]]  ... 이렇게 될 것이다.

한 번 풀어보자.
주의할 점이 있다.
long long형을 써야하고, 칸의 숫자가 0인 경우의 처리가 필요할 것 같다.
AC를 받았다.