[AlgoSpot] 외발뛰기

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
문제 링크

문제 풀이

• 동적 계획법을 이용하여 풀이하였다.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int[][] map;
    public static int[][] chk;
    public static int C, N;

    public static int dp(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N) return 0;
        if (x == N-1 && y == N-1) return 1;
        if (chk[x][y] != -1) return chk[x][y];
        int jumpSize = map[x][y];
        return chk[x][y] = (dp(x + jumpSize, y) | dp(x, y+jumpSize));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        map = new int[101][101];
        chk = new int[101][101];
        C = scanner.nextInt();
        for (int c = 0; c < C; c++) {
            N = scanner.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = scanner.nextInt();
                    chk[i][j] = -1;
                }
            }
            System.out.println(dp(0, 0)==1? "YES" : "NO");
        }

    }
}