백준 1890번 - 점프

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

dp를 이용한 경로의 수 문제이다.

bottom up 방식으로 풀 수 있고 top down 방식으로 풀 수 있는데

top down방식을 이용해 재귀 호출하여 문제를 풀었다.

dfs로 해당 거리 만큼 가다가

먼저 목적지에 도달하면 1을 리턴해 주면 된다.

주의할 점은 이미 방문한 지점을 visited로 체크하지 않으면 시간초과가 나기 때문에

이미 방문한 지점은 다시 호출할 수 없도록 해준다.

그리고 목적지 뿐만 아니라 다른 지점도 0값이 있기 때문에

목적지가 아닌 이상 0이 나오면 갈 수 없도록 0을 리턴해줘야 한다.

마지막으로

이런 예외 처리를 모두 해주었는데 오류가 나다가 타입을 바꿔서 해결할 수 있었는데

경우의 수가 2^64-1이기 때문에 int타입이 아닌 long타입으로 값을 리턴해줘야

올바른 답이 나온다.

#include <iostream>
using namespace std;
 
int N;
int map[100][100]={0};
long dp[100][100]={0};
int visited[100][100]={0};
 
int dy[2]={1,0};
int dx[2]={0,1};
 
long dfs(int y,int x){
    
    if(y==N-1 && x==N-1){
        return 1;
    }
    
    if(map[y][x]==0)
        return 0;
    
    if(visited[y][x] || dp[y][x]){
        return dp[y][x];
    }
    
    visited[y][x]=1;
    for(int i=0;i<2;i++){
        int ny=y+dy[i]*map[y][x];
        int nx=x+dx[i]*map[y][x];
 
        
        if(ny>=N || nx>=N)
            continue;
        
        dp[y][x]+=dfs(ny,nx);
    }
    
    return dp[y][x];
}
int main(){
    
    cin>>N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j]);
        }
    }
    
    cout<<dfs(0,0)<<endl;
    return 0;
}