백준 1890. 점프 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/1890

"DP 와 2^63"

전형적인 DP 문제로서 Top-down 방식의 메모이제이션을 사용한다. Start 부터 시작해서 End 까지 탐색한다. 검색 중에 End 에 도착했다면 한 가지 방법이 있는 것이므로 1을 리턴하고 이 값은 함수를 호출한 dp[x] 에 누적된다. 아래 예를 보면 4,5,6 번 노드가 이와 같다. 

이런식으로 "누적"을 하게 되면 해당 노드에서 End로 갈 수 있는 방법의 수가 dp[x]에 저장된다. 

DFS 나 BFS 로 풀면 시간초과가 날 것이 왜 dp를 쓰면 시간이 단축 되나? 라는 질문에 답은 7번 노드를 보면 된다. 7번 노드까지 탐색한 후에 6번 노드의 dp값을 체크하였더니 1이 저장되어 있더라. 6번 이후에는 탐색할 필요가 없다. (DFS 나 BFS 같으면 계속 탐색함.)

아래 예에서는 6번 노드 뒤에 한 번의 탐색으로 End에 가지만, 만약 6번 노드와 End 노드 사이에 1억개의 노드가 있다면... 게다가 6번 노드로 오는 노드가 7번 노드 뿐만 아니라 엄청나게 많은 노드가 6번 노드로 이어진다면... 그 연산수는 엄청 늘어날 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    static int N;
    static int[][] map;
    static long[][] dp;
    static int[] dx = {0,1};
    static int[] dy = {1,0};
    
    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dp[i], -1);
        }
        
        System.out.println(solve(0,0));
    }
    
    static long solve(int x, int y) {
        
        if(dp[x][y] != -1)
            return dp[x][y];
        
        if(x == N-1 && y == N-1) {
            return 1;
        }
        
        if(map[x][y] == 0) 
            return 0;
        
        dp[x][y] = 0;
        for (int i = 0; i < 2; i++) {
            int nx = x + dx[i]*map[x][y];
            int ny = y + dy[i]*map[x][y];
            
            if(!isRange(nx, ny))
                continue;
            
            dp[x][y] += solve(nx,ny);
        }
        return dp[x][y];
    }
 
    static boolean isRange(int x , int y) {
        if(  x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
    
}