[1890] 점프

http://boj.kr/1890

DP - basic

D[i][j] : (1, 1)에서 (i, j) 까지 오는 방법의 수

< 소스코드 >

#include <stdio.h>
 
int n;
int g[101][101];
long long d[101][101];
 
long long jump(int r, int c)
{
    int k = g[r][c];
    long long ret = 0;
    if(r == n && c == n) return 1;
    if(r > n || c > n || k == 0) return 0;
    if(d[r][c] != -1) return d[r][c];
 
    ret += jump(r+k, c);
    ret += jump(r, c+k);
    return d[r][c] = ret;
}
 
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=n; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = 1LL*(-1);
        }
    }
    printf("%lld\n", jump(1, 1));
    return 0;
}
 

>> 10 : ret 를 int 로 선언해서 81%에서 틀렸었다....

< 과거 소스코드 >

#include <stdio.h>
 
int g[101][101];
long long d[101][101];
 
long long go(int i, int j)
{
    int k;
    if(i<1 || j<1) return 0;
    if(i==1 && j==1) return 1;
    if(d[i][j]) return d[i][j];
 
    for(k=0; k<j; k++)
        if(k+g[i][k] == j)
            d[i][j] += go(i, k);
 
    for(k=0; k<i; k++)
        if(k+g[k][j] == i)
            d[i][j] += go(k, j);
 
    return d[i][j];
}
 
int main()
{
    int n, i, j;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    printf("%lld\n", go(n, n));;
 
    return 0;
}
 
 

>> 역시 재귀로 풀었지만, go(n, n) 으로 시작해서 불필요하게 머리를 더 쓴거 같다..