외발 뛰기 - DP

아래는 종만북의 DP의 메모이제이션 코드 패턴이다.

//메모이제이션 사용 예

//전부 -1로 초기화
int cache[2500][2500]

//a와 b는 각각 [0,2500) 구간 안의 정수
//반환 값은 항상 int형 안에 들어가는 양수
int someObscureFunction(int a, int b) {
	//기저 사례 처리
	if(...) return ...;
    
    //답을 구한적이 있으면 곧장 반환
    if(cache[a][b] != -1) return cache[a][b];
    
    //답을 구한적이 없으면 여기서 답을 계산
    cache[a][b] = ...;
    return cache[a][b];
}

 

외발뛰기 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int testcase = Integer.parseInt(br.readLine());

        for(int t=0; t<testcase; t++) {
            int n = Integer.parseInt(br.readLine());
            int[][] matrix = new int[n][n];
            int[][] dp = new int[n][n];

            for(int i=0; i<n; i++) {
                st = new StringTokenizer(br.readLine()," ");
                for(int j=0; j<n; j++) {
                    matrix[i][j] = Integer.parseInt(st.nextToken());
                    dp[i][j] = -1;
                }
            }
            int result = f(0,0,matrix,dp);
            if(result == 0) System.out.println("NO");
            else System.out.println("YES");
        }
    }

    static int f(int x, int y, int[][] matrix, int[][] dp) {
        if (x >= matrix.length || y >= matrix.length) return 0;
        if (x == matrix.length - 1 && y == matrix.length - 1) return 1;

        if (dp[x][y] != -1) return dp[x][y];
        dp[x][y] = f(x + matrix[x][y], y, matrix, dp) + f(x, y + matrix[x][y], matrix, dp);
        return dp[x][y];
    }
}