[백준] 점프 - 실패

참고 : www.acmicpc.net/problem/1890

 

- dp 문제

- dp 시도하다가 안되서 dfs로 풀려다 시간초과

- top-down 방식 좀 더 자유롭게 쓸 수 있게

 

import java.io.*;
import java.util.*;
class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean isInside(int N) {
        return this.x >= 0 && this.y >= 0 && this.x < N && this.y  < N;
    }

}
public class Solution {
    private static int N;
    private static int count;
    private static int[][] block;
    private static int[][] dp;
    private static int[] dx = new int[]{0, 1};
    private static int[] dy = new int[]{1, 0};

    private static int dfs(int x, int y) {
//        System.out.println("x: " + x+ " y: " + y);
        if(x == N-1 && y == N-1) {
            count++;
            return 1;
        };
        for(int i=0; i<2; i++) {
            int nextStep = block[x][y];
            int nx = x + dx[i] * nextStep;
            int ny = y + dy[i] * nextStep;
            Point p = new Point(nx, ny);
            if(p.isInside(N)) {
                dp[nx][ny] += dp[x][y];
                dfs(nx, ny);
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        block = new int[N][N];
        dp = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                block[i][j] = sc.nextInt();
            }
        }
        dfs(0, 0);
//        System.out.println(dp[N-1][N-1]);
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < N; j++) {
//                System.out.println(dp[i][j]);
//            }
//        }
        System.out.println(count);

    }
}