[백준/1890] 점프 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 점프

🦧 문제 풀이 접근

N x N dp 배열을 만든다.
입력받은 숫자 만큼 오른쪽, 아래로 이동 가능한 칸이 있을 경우 현재 칸 만큼 더해준다.

dp[i+num][j] += dp[i][j]
dp[i][j+num] += dp[i][j]

💻 code

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

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];
        dp[0][0]=1;
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++) {
                int num=Integer.parseInt(st.nextToken());
                if(num==0)
                    continue;
                if(i+num<N)
                    dp[i+num][j] += dp[i][j];
                if(j+num<N)
                    dp[i][j+num] += dp[i][j];
            }
        }
        System.out.println(dp[N-1][N-1]);
    }
}

🥇 결과

🎓 느낀점

dp 배열의 크기를 long으로 설정해야 통과할 수 있다.