[백준] 1890 점프 JAVA 정답 코드

import java.io.*;

public class Main {

    static int[][] board;
    static int size;
    static boolean[][] isConcluded;
    static long[][] dp;

    static int[] mRow = {0, -1};
    static int[] mCol = {-1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        size = Integer.parseInt(br.readLine());
        board = new int[size][size];
        isConcluded = new boolean[size][size];
        dp = new long[size][size];
        isConcluded[0][0] = true;
        dp[0][0] = 1;

        for (int i = 0; i < size; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < size; j++) {
                board[i][j] = Integer.parseInt(input[j]);
            }
        }

        bw.write(getDp(size - 1, size - 1)+"");
        bw.flush();
    }

    static long getDp(int r, int c) {

        if (isNotRange(r, c)) //범위에 있는가?
            return 0;
        if (isConcluded[r][c]) //dp 적용 가능한가?
            return dp[r][c];

        long sum = 0; // 자료형 int 가 아니라 long 으로 해야 오버 플로우가 발생 x

        /*
        dp[r][c]는 dp[r- move][c] + dp[r][c - move] + ... 의 합이다.
        다시말해 왼쪽에서 올 수 있는 경우와 위에서 올 수 있는 경우를 모두 합한 값.
         */

        for (int len = 1; len <= Math.max(r, c); len++) {
            for (int i = 0; i < 2; i++) {
                int nR = r + len * mRow[i];
                int nC = c + len * mCol[i];

                if (isNotRange(nR, nC)) continue;
                if (board[nR][nC] == len) { // 보드의 값이 이동한 거리와 같아야한다는 조건
                    if (isConcluded[nR][nC]) // 이미 계산된 경우면 dp 적용
                        sum += dp[nR][nC];
                    else //아니면 계산함
                        sum += getDp(nR, nC);
                }
            }
        }

        // dp 적용
        isConcluded[r][c] = true;
        dp[r][c] = sum;
        return sum;
    }

    private static boolean isNotRange(int r, int c) {
        return r >= size || r < 0 || c >= size || c < 0;
    }

}