BOJ : 1890 점프

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

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번

DP로 해결가능한 문제다.

0,0에 1을 넣고 

반목문을 돌면서 오른쪽, 아래로 이동 가능한 곳의 값을 더해준다. (dp값은 그 좌표에 도달 가능한 루트의 개수이다.)

유의할 점은 jump값을 더할 때 N의 값을 초과하지 않는지, N-1, N-1 은 연산을 제외 했는지, 경로의 개수를 고려했는지  이 정도 되겠다.

경로의 개수가 많아 BFS로 풀게 되면 메모리 초과가 나오지 않을까 싶다.

#include <stdio.h>

int N;
int map[101][101];
long dp[101][101]={0,};
bool visited[101][101];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    
    dp[0][0]=1;
    visited[0][0]=true;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!visited[i][j]) continue;
            if(i==N-1 && j==N-1) break;
            int jump=map[i][j];
            if(i+jump < N){
                dp[i+jump][j] += dp[i][j];
                visited[i+jump][j] = true;
            }
            if(j+jump < N){
                dp[i][j+jump] += dp[i][j];
                visited[i][j+jump] = true;
            }
        }
    }
    

    printf("%ld\n",dp[N-1][N-1]);
}