[BOJ] 3372. 보드 점프

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int map[][] = new int [N][N];
		BigInteger memo[][] = new BigInteger [N][N];
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				map[y][x] = sc.nextInt();
			}
		}
		
		for (int i = 0; i < memo.length; i++) {
			for (int j = 0; j < memo.length; j++) {
				memo[i][j] = new BigInteger("-1");
			}
		}
		
		System.out.println(solve(0,0,map,memo,N));
	}
	
	public static BigInteger solve(int y,int x,int map[][],BigInteger memo[][],int N) {
		if(x < 0 || x > N-1 || y < 0 || y > N-1) return BigInteger.ZERO;
		if(y == N-1 && x == N-1) return BigInteger.ONE;
		if(map[y][x]==0) return BigInteger.ZERO;
		if(!memo[y][x].equals(new BigInteger("-1"))) return memo[y][x];
		BigInteger rightCnt = solve(y,x+map[y][x],map,memo,N);
		BigInteger downCnt = solve(y+map[y][x],x,map,memo,N);
		memo[y][x] = rightCnt.add(downCnt);
		return memo[y][x];
	}
}