[JUMPGAME] 외발뛰기

### DP ###

[JUMPGAME] 외발뛰기 : https://algospot.com/judge/problem/read/JUMPGAME

<소스코드>

#include <stdio.h>
 
int n;
int g[101][101], d[101][101];
 
int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) + jump(r, c+g[r][c]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = -1;
            }
        }
 
        jump(0, 0) ? puts("YES") : puts("NO");
    }
    return 0;
}

>> 기본 DP 문제. jump(r, c) : r, c 까지 점프해서 (n-1, n-1) 로 갈 수 있는지 여부. (0, 0 시작이므로..)

>> d[i][j] = 0 으로 초기화 하면 시간초과가 발생한다..

- 종만북 풀이 

int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) || jump(r, c+g[r][c]);
}

>> jump() 에서 6번라인을 || 로 처리하였다...!!

>> 첫번째 코드는 16ms 가 나왔는데, || 로 변경한 코드는 8ms 가 나왔다..!!

- 1년전 코드.

#include <cstdio>
 
int g[101][101], d[101][101];
 
int jump(int y, int x)
{
    int i, ans=0;
    int &ret = d[y][x];
    if(y < 1 || x < 1) return 0;
    if(y == 1 && x == 1) return 1;
    if(ret) return ret;
    
 
    for(i=1; i<x; i++)
        if(g[y][x-i]==i)
            ans += jump(y,x-i);
    
    for(i=1; i<y; i++)
        if(g[y-i][x]==i)
            ans += jump(y-i,x);
    return ret = ans;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, n;
        scanf("%d", &n);
        
        for(i=1; i<=n; i++) {
            for(j=1; j<=n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = 0;
            }
        }
        
        jump(n, n) ? puts("YES") : puts("NO");
    }
}

>> jump(n, n) 으로 시작했다. 굳이 이럴필요가 없었는데, 거꾸로 타고 가는 것을 고집했던 것 같다.