[백준 1890] 점프

 

 

메모이제이션 + 탐색을 요구하는 문제다.

 

1. 경로의 개수가 21억즈음이므로 메모이제이션 없이 돌리면 시간초과가 난다.

 

2. 아래, 오른쪽으로 가는 경로의 개수를 합하면서 이동하기 때문에 dp 배열은 long으로 해줘야 한다.

 

3. 게임판 배열은 0<=N[i][j]<=9 이므로 점프를 안하게 되었을때는 예외처리를 해주어야 한다.

 

 

탑다운 방식으로 구현했다.

 

public class Main {
    
    static int a[][];
    static long dp[][];
    static int n;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        a = new int[n][n];
        dp = new long[n][n];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                a[i][j] = sc.nextInt();
        
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                dp[i][j] = -1;
        
        System.out.println(recursive(0, 0));
    }
    
    public static long recursive(int x, int y) {
        if(x == n-1 && y == n-1) return 1;
        if(x >= n || y >= n) return 0;
        if(a[x][y] == 0) return 0;
        if(dp[x][y] != -1) return dp[x][y];
        
        int dist = a[x][y];
        long result = recursive(x+dist, y) + recursive(x, y+dist);
        dp[x][y] = result;
        return result;
    }
}