[백준 3372] 보드 점프 - JAVA

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

 

dp는 쉬운데 큰 수를 연산해야 한다. 

 

경로의 개수는 2^63-1보다 클 수 있으며, 100자리를 넘지는 않는다. => long 범위 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    int[][] a = new int[N][N];
    BigInteger[][] dp = new BigInteger[N][N];

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        a[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        dp[i][j] = new BigInteger("0");
      }
    }
    dp[0][0] = new BigInteger("1");

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {

        int d = a[i][j];

        if (d == 0) {
          continue;
        }

        if (i + d < N) {
          dp[i + d][j] = dp[i + d][j].add(dp[i][j]);
        }
        if (j + d < N) {
          dp[i][j + d] = dp[i][j + d].add(dp[i][j]);
        }
      }
    }

    System.out.println(dp[N - 1][N - 1]);
  }
}