백준 1890 / 점프

우선, 경로의 개수의 최대값이 2^63-1이니 BFS로 풀면 메모리초과가 난다. (ex) 모든 칸이 1로된 100x100 게임판)

다이나믹 프로그래밍으로 풀어야 한다.

d[i][j]가 i,j에 도착할 수 있는 모든 경우의 수라고 했을때,

0보다 크고 i보다 작은 어떠한 k에 대해서

map[k][j] + k가 i가 되는 경우를 찾는다면, 

d[i][j]는 d[k][j]로 이루어질 것이다. 또한,

map[i][k] + k가 j가 되는 경우를 찾는다면

d[i][j]는 d[i][k]로 이루어질 것이다.

d의 값에 2^63-1이 들어갈 수 있으니 d는 long이상을 선언해주어야한다.

코드 (34~43번째 코드가 핵심)

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int map[101][101];
long long d[101][101];
 
int dx[] = { 1,0 };
int dy[] = { 0,1 };
 
int ans = 0;
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    d[0][0] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            
            for (int k = 0; k < i; k++) {
                if (map[k][j] + k == i) {
                    d[i][j]+=d[k][j];
                }
            }
 
            for (int k = 0; k < j; k++) {
                if (map[i][k] + k == j) {
                    d[i][j]+=d[i][k];
                }
            }
 
        }
    }
 
    
    cout << d[n - 1][n - 1];
}