[boj] 백준 1890 점프 (Java) - dp

[문제]

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

1890번: 점프

 

[풀이]

가장 왼쪽 위 칸에서 시작해서 아래쪽, 오른쪽으로만 이동 가능하다. 가장 왼 쪽 윗 칸에서 이동한 경우만 dp에 반영해주기 위해 dp[0][0] = 1로 둔다.

2중 for문을 돌면서 아래로 이동할 수 있는 경우, 즉 i+move가 범위 안에 있는 경우 dp[i+move][j] += dp[i][j] 이고, 오른쪽으로 이동할 수 있는 경우, 즉 j+move가 범위 안에 있는 경우 dp[i][j+move] += dp[i][j] 이다.

 

경로의 개수는 2^63-1보다 작거나 같다고 되어있으므로 dp는 long 배열로 선언한다.

 

[코드]

 

package dp;

import java.io.*;
import java.util.*;

public class boj_1890_점프 {
    static int n;
    static int[][] board;
    static long[][] dp;
    public static void main(String[] args) throws Exception{
        //가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        dp = new long[n][n];
        StringTokenizer st;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        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 move = board[i][j];
                if (i + move < n) { //아래로 이동 가능
                    dp[i + move][j] += dp[i][j];
                }
                if (j + move < n) { //오른쪽으로 이동 가능
                    dp[i][j + move] += dp[i][j];
                }
            }
        }
        
        System.out.println(dp[n-1][n-1]);
    }


}