BOJ) 점프

점프

1890번: 점프

풀이

 

0,0을 시작으로 n-1,n-1까지 도달할 수 있는 경우의 수를 구하는 문제다.

각 인덱스에 적혀있는 칸만큼 오른쪽 혹은 아래로 움직일 수 있으며, 범위 밖으로는 움직일 수 없고 칸에 적힌만큼 정확히 이동해야한다.

그래서 모든 인덱스를 순차적으로 돌면서 dp 값이 0이 아니고, 해당 인덱스가 움직일 수 있는 값이 0이 아닐 때, dp를 최신화해줬다.

경우의 수를 누적시키며 답을 찾아간다고 생각하면 된다.

 

처음에는 dfs로 풀려고 생각하다가, 경로의 개수가 최대 2^63 -1이기 때문에 포기했다.

그리고 int의 최대값을 넘어가는 범위가 포함되기 때문에 dp는 long 타입으로 설정해줬다.

 

코드

 

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());
        int[][] map = new int[n][n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)  map[i][j] = Integer.parseInt(st.nextToken());
        }
        br.close();
        solution(n,map);
    }

    private static void solution(int n, int[][] map) {
        long[][] dp = new long[n][n];
        dp[0][0] =1;
        for(int y=0; y<n; y++) {
            for(int x=0; x<n; x++) {
                if(dp[y][x] !=0 && map[y][x] !=0) {
                    int step = map[y][x];
                    if(isInArea(x+step,y,n))    dp[y][x+step] += dp[y][x];
                    if(isInArea(x,y+step,n))    dp[y+step][x] += dp[y][x];
                }
            }
        }
        System.out.println(dp[n-1][n-1]);
    }

    private static boolean isInArea(int x,int y, int n) {
        return x<n && y<n;
    }
}