[백준] 1890번 점프 java

문제 풀이 과정

1. 메모리를 사용하기 위해 게임판과 똑같은 모양의 dp[n][n] 배열 생성
2. dp[i][j] = 해당 위치까지 올 수 있는 경로의 수라고 정의함
3. 직접 예제 입력1 케이스를 그려보면서 패턴을 찾음

차례대로 dp배열을 순회하며 dp[i][j]값이 0이 아닌 경우 경로 누적 수행.
(dp[i][j]값이 0인 경우는 해당 경로로 올 수 없다는 것)

nextY = i + board[0][0] = 아래로 점프했을 때,
nextX = i + board[0][0] = 오른쪽으로 점프했을 때,
점프했을 때 좌표가 범위 안에 포함되면 현재 dp 경로 값을 다음 점프했을 때 dp 경로 값에 더해줌.

점화식
if(nextY<n) dp[nextY][j]+=dp[i][j];
if(nextX<n) dp[i][nextX]+=dp[i][j];

• 처음 dp[0][0] = 1로 출발
  1 0 0 0
  0 0 0 0
  0 0 0 0
  0 0 0 0

• dp[0][0]
  1 0 1 0
  0 0 0 0
  1 0 0 0
  0 0 0 0

• dp[0][2]
  1 0 1 0
  0 0 0 0
  1 0 0 0
  0 0 1 0

• dp[2][0]
  1 0 1 0
  0 0 0 0
  1 1 0 0
  1 0 1 0

• dp[2][1]
  1 0 1 0
  0 0 0 0
  1 1 0 1
  1 0 1 0

• dp[2][3]
  1 0 1 0
  0 0 0 0
  1 1 0 1
  1 0 1 1

• dp[3][0]
  1 0 1 0
  0 0 0 0
  1 1 0 1
  1 0 1 2

• dp[3][2]
  1 0 1 0
  0 0 0 0
  1 1 0 1
  1 0 1 3

중요

dp 풀면서 항상 따져야할 것

• 초기값이 적절한가
• 범위 오류가 없는가
• 누적값을 이용하고 있는지
  이 문제에서 처음에는 경로를 1씩 더해주기만 하고 현재 dp값을 누적해주지 않는 실수를 함, 1씩 더해주기만 하면 중복 경로가 무시됨
  예 : 2 -> 5 -> 도착, 1 -> 5 -> 도착일 경우 도착 경로는 2개이지만 1개로 저장이된다.
  
• 타입 실수 (경로가 2^63-1만큼 가능하므로 long타입으로 써야함..)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int board[][] = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0; j<n; j++)
                board[i][j]=Integer.parseInt(st.nextToken());
        }

        long dp[][] = new long[n][n];
        // 초기값
        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 || board[i][j]==0) continue;
                if(dp[i][j]>0){
                    int nextY = i+board[i][j];
                    int nextX = j+board[i][j];
                    if(nextY<n) dp[nextY][j]+=dp[i][j];
                    if(nextX<n) dp[i][nextX]+=dp[i][j];
                }
            }
        }

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