[BOJ_1890] 점프

설명

---

아래 또는 오른쪽로만 움직일 수 있는 경우로 고정 되어 있습니다. 따라서, 점화식을 2차원 배열로 만들기 쉬운데요.

 

dp를 해당 케이스로 가는 경우의 수로 고려하고 문제를 풀이를 시도하면 쉽게 세울 수 있는 DP 문제이나 처음에 점화식을 생각해내는 것이 역시 어렵습니다.

 

코드

---

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

public class BOJ_1890 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        long[][] dp = new long[N][N];
        int moveMentsCnt = 0;
        dp[0][0] = 1;
        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine(), " ");
            for (int j = 0; j < N; j++){
                moveMentsCnt = Integer.parseInt(tk.nextToken());
                if(moveMentsCnt > 0){
                    if(i + moveMentsCnt < N) {
                        dp[i + moveMentsCnt][j] += dp[i][j];
                    }
                    if(j + moveMentsCnt < N) {
                        dp[i][j + moveMentsCnt] += dp[i][j];
                    }
                }
            }
        }
        System.out.println(dp[N - 1][N - 1]);
    }
}

 

1890번: 점프