코딩 테스트 풀이 20 - 점프

✔ 문제

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

💡 접근 방법

각 타일에 갈 수 있는 경우의 수를 지속적으로 계산하여 더한다.

⭐ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long[][] dp = new long[n][n];
        int[][] jumps = new int[n][n];

		// Receive Input
        for (int i = 0; i < n ; ++i)
        {
            String[] jumpStr = br.readLine().split(" ");
            for (int j = 0; j < n ; ++j)
            {
                jumps[i][j] = Integer.parseInt(jumpStr[j]);
            }
        }

		// Start
        dp[0][0] = 1;

        for (int i = 0 ; i < n ; ++i)
        {
            for (int j = 0 ; j < n ; ++j)
            {
                if (i == n-1 && j == n-1)
                    continue;

                int currentJump = jumps[i][j];
				
                // 밖으로 나가지 않는다면 해당 타일의 경우의 수에 현재 타일에 갈 수 있는 경우의 수를 더한다. 
                if (i + currentJump < n)
                    dp[i+currentJump][j] += dp[i][j];

                if (j + currentJump < n)
                    dp[i][j+currentJump] += dp[i][j];
            }
        }


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