[백준 1890] 점프 -JAVA // le_effort//

 

알고리즘 DP

 

주의할 점 경로의 개수가 2^63 -1 

이니 

dp 배열을 long 형태로 받아야 한다.

 

dp [i][j] = 이 칸 까지 올 수 있는 경우의 수들.

 

일단 첫 시작 지점 dp [0][0] = 1로 둔다.

그 이유는 아래에서 설명한 조건을 다 충족 할 시 개수를 늘려줘야 하는데

0으로 두면 계속 0 이 되기때문이다.

 

문제에서 오른쪽/ 아래쪽으로 정해진 칸만큼 갈 수 있다 했으니 

dp [i][j] 기준으로

 

아래쪽으로 갈 때 

i+정해진 칸 <n 일 경우 갈 수 있으므로 (정해진 칸 = map [i][j])

dp [i+정해진 칸][j] += dp [i][j]

기존 dp [i][j]에서 i+정해진 칸[i]을 하면 그만큼 아래쪽으로 가겠죠?

 

오른쪽으로 갈 때

j+정해진 칸 <n 일 경우 갈 수 있으므로 (정해진 칸 = map [i][j])

dp [i][j+정해진 칸]+= dp [i][j]

 

또 i==n-1 && j==n-1 일 경우 따로 continue 처리를 해줘야 하는데

해주지 않으면 마지막 칸은 0으로 지정되어 있으니

dp [n-1+0][n-1+0]을 해도 범위에 지정됨으로

dp [n-1][j-1]의 값이 계속 더해짐으로 빼야 한다

 

더 자세히 설명하자면,

   if(i+map [i][j]<n) {

       dp [i+map [i][j]][j] += dp [i][j];

      }

i == n-1이고 j == n-1  map [i][j]  == 0; 

이렇게 있다면  저 코드에서     

dp [n-1 + 0] [j] += dp [n-1][n-1] 

즉 dp[n-1][n-1] += dp[n-1][n-1] 

이런 식으로 값이 중복돼서 더해지기 때문이다.

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static int map[][];
    static long dp[][];
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new long[n][n];
        
        for(int i=0; i<n; i++) {
            String[] t = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(t[j]);
            }
        }
        dp[0][0]=1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i==n-1 && j==n-1) {
                    continue;
                }
                if(i+map[i][j]<n) {
                    dp[i+map[i][j]][j] += dp[i][j];
                }
                if(j+map[i][j]<n) {
                    dp[i][map[i][j]+j]+=dp[i][j];
                }
            }
        }
        System.out.println(dp[n-1][n-1]);
    }
}