📝문제

처음 문제를 봤을 때는 DFS 풀이법이 떠올랐다.
하지만 구하는 답의 크기가 최대 2^63-1이고 배열의 크기도 최대 100 X 100으로 DFS를 쓰면 시간초과가 날 거 같았다. 그래서 DP를 쓰기로 했고, DP를 풀 때 항상 그렇듯 점화식을 생각해내는데 가장 많은 시간이 걸렸다.
처음에는 해당 인덱스에 도착하면 현재의 값 +1을 했는데 그렇게하면 틀린 답이 출력된다.
이중for문으로 dp 배열을 돌기 때문에 dp의 해당 인덱스는 딱 한번만 방문한다. 내가 처음에 생각했던 방법은 모든 경로의 track을 따라간다고 잘못 생각했던 것이다.
따라서 dp 배열을 탐색하면서 다음 이동 지점에는 해당 dp의 값을 더해줘야 되는 것이다.

점화식

• dp[i+map[i][j]][j] = dp[i+map[i][j]][j] + dp[i][j] //오른쪽으로 이동하는 경우
• dp[i]j+map[i][j]] = dp[i]j+map[i][j]] + dp[i][j] //아래쪽으로 이동하는 경우

📌코드

package Baekjoon;

import java.io.*;
import java.util.*;

public class BOJ1890 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[][] map = new int[n][n];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        long[][] dp = new long[n][n];
        /**
         * 점화식...
         * dp 배열에는 해당 인덱스에 몇 번 왔는지 기록
         * dp[i][j]에 왔을 때, dp[i+map[i][j]][j]와 dp[i][j+map[i+j]를 dp[i][j]만큼 증가
         */
        dp[0][0] = 1;
        for(int i = 0; i< n; i++){
            for(int j = 0; j < n; j++){
                if(dp[i][j] > 0 && map[i][j] > 0){
                    if(i+map[i][j] < n){
                        dp[i+map[i][j]][j] += dp[i][j];
                    }
                    if(j+map[i][j] < n){
                        dp[i][j+map[i][j]] += dp[i][j];
                    }
                }
            }
        }
        System.out.println(dp[n-1][n-1]);
    }
}