백준 1890 점프

https://www.acmicpc.net/problem/1890

• 다이나믹 프로그래밍

• 풀이

1. dp 배열과 정답 배열 두개를 만들고, dp 배열에서 오른쪽과 아래로 이동했을 때, 숫자가 N보다 크지 않으면 정답 배열에 경우의 수 합을 넣는다.
   (arr[i+d[i][j]][j]+=ans[i][j])
2. 마지막 (N,N)칸에서 한번 더 경우의 수들을 더해주지 않도록 한다.
   if .... !(i==N and j==N)
3. 값이 int보다 커질 수 있으므로 long long 자료형을 사용한다.

• 코드

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

ll N;
ll d[101][101], ans[101][101];

int main(void){
    fast;
    cin>>N;
    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            cin>>d[i][j];
        }
    }
    memset(ans,0,sizeof(ans));
    ans[1][1]=1;
    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            if(i+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i+d[i][j]][j]+=ans[i][j];
            if(j+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i][j+d[i][j]]+=ans[i][j];
        }
    }
    cout<<ans[N][N];
}