JUMPGAME (하, p. 215)

매우 기초적인 DP문제

기초적인 DP라고 하면, 항상 Knapsack이나 타일채우기 같은 문제를 풀었는데,

이런 형태의 문제는 처음 풀어보는 느낌이었음.

난이도는 매우 낮았지만, 나름 재밌는 문제였음.

(x,y)에서 끝 지점에 갈 수 있는지 없는지를 dp[x][y]에 기록함.

#include <bits/stdc++.h>
using namespace std;
int n;
int v[101][101];
int dp[101][101];
int f(int x, int y) {
    if(x<0||y<0||x>=n||y>=n) return 0;
    if(dp[x][y]>=0) return dp[x][y];

    int & ret = dp[x][y];
    ret=0;
    if(f(x+v[x][y],y)==1) ret=1;
    if(f(x,y+v[x][y])) ret=1;
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        memset(dp,-1,sizeof(dp));
        cin >> n;
        dp[n-1][n-1]=1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                cin >> v[i][j];
            }
        }

        if(f(0,0)) puts("YES");
        else puts("NO");
    }
    return 0;
}