[백준 java] 1890 - 점프

1890번: 점프

---

dp에 경로의 수를 저장하면서 도착 경로의 수를 구하는 문제이다.

 

원래는 해당 경로를 지났다는 표시만 하고 board[ i ] [ j ] 의 다음 목적지인 아래값이

x 축으로 이동하면 board[ i + board[ i ] [ j ] ] [ j ] 

y 축으로 이동하면 board[ i ] [ j +  board[ i ] [ j ] ] 

목적지인 board[ N-1 ] [ N-1 ] 에 도달하면 count ++ 하는 방식으로 계산했는데

이렇게 하면 이전에서 겹치는 노드를 계산 할 수 없어서 실패.

 

 

문제풀이

이후에 dp 에 해당 노드에 도달한 수를 저장하는 방법으로 구현하였고 

dp[ 0 ] [ 0 ] = 1로 초기값을 두고 다음 목적지 노드를 밟을때 해당 노드의 dp에

현재 노드 값을 더해가며 이동한 모든 노드의 합을 저장하였다

board[ 2 ] [ 2 ] 까지 가는 경우의 수는 2가지가 있으니 DP[ 2 ] [ 2 ] 의 값은 2이다

 

따라서 마지막 dp[ N-1 ][ N-1 ] 노드는 해당 노드까지의 모든 경우의 수를 저장하게 된다

 

 

 

주의할점

1. 경로의 수 값은 2^63 - 1 보다 작거나 같으니 DP가 int타입이면 에러가 발생한다
2. 다음 목표의 노드가 N-1 x N-1 크기를 벗어나는것을 주의하자

---

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

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

public class B1890 {
    static int N;
    static int[][] board;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        board = new int[N][N];
        dp = new long[N][N];

        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;
        jump();
    }

    private static void jump() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(dp[i][j] == 0) continue;
                if(i == N-1 && j == N-1) {
                    break;
                }
                if(board[i][j]+i < N){
                    dp[board[i][j]+i][j] += dp[i][j];
                }
                if(board[i][j]+j < N){
                    dp[i][board[i][j]+j] += dp[i][j];
                }
            }
        }


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