[백준 3372] 보드 점프

알고리즘

• DFS
• DP

풀이 방법

• 해멧던 부분 :
  • DFS 로 했다가 메모리 초과가 남.
  • 메모리 초과를 → dp로 바꿈.
  • 하향식에 실패해서 상향식으로 바꿈.
  • 2^63보다 큰 숫자는 long으로 해결이 안됨. bigInteger를 써야 함.
  • BigIntger 를 처음에 0으로 초기화 해줬는데 메모리 초과가 남.
  • BigInteger 배열은 처음에 Null로 초기화 되어 있음. 따라서 이때 null이 아닐 경우 바로 계산된 값 반환해야 함.

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st = null;
    public static int[][] arr;
    public static BigInteger[][] dp;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        dp = new BigInteger[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(dfs(0, 0, n));
    }
    private static BigInteger dfs(int x, int y, int n) {
        if (x == n - 1 && y == n - 1) return BigInteger.ONE;
        if (dp[x][y] != null) return dp[x][y]; // 이미 계산된 값 반환
        dp[x][y] = BigInteger.ZERO; // 초기값 설정
        for (int i = 0; i < 2; i++) {
            int nextX = x + dx[i] * arr[x][y];
            int nextY = y + dy[i] * arr[x][y];
            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
                dp[x][y] = dp[x][y].add(dfs(nextX, nextY, n));
            }
        }
        return dp[x][y];
    }
    public static int dx[] = {1, 0};
    public static int dy[] = {0, 1};
}