1890 점프

처음에 그냥 DFS로만 풀었다가 시간초과가 났다.

N이 100정도 되기 때문에 DFS로는 시간 초과가 해결이 안된다. 따라서 DP를 적용하여 풀어야만 한다.

DP[x][y] 를 -1로 초기화 해두고, 방문하는 좌표에 0을 넣어 준다.(그래야지 방문했는지 안했는지 알 수 있다.)

DP[x][y]는 (x,y)를 지나서 (n,n) 까지 도달 할 수 있는 경로를 저장해준다고 생각하면 된다.

그렇기 때문에 다른 경로를 통해 (x,y)를 다시 방문하였을 때는 더 탐색하지 않고 해당 값만 return 해주면 된다!

그렇게 되면 DP[0][0]에는 (0,0) ~ (n,n) 까지의 경로가 저장되게 된다.

코드:

#include <iostream>

using namespace std;

typedef long long lld;

int N;

int map[101][101];

int V[101][101];

lld cnt;

int px[2] = {1, 0 }; // up left down right

int py[2] = {0, 1 };

lld dp[101][101];

// return count of path

lld dfs(int x, int y){

if (x == N - 1 && y == N - 1){

return 1;

}

if (dp[x][y] != -1) 

return dp[x][y];

dp[x][y] = 0;

for (int i = 0; i < 2; i++){

int nx = x + (map[x][y] * px[i]);

int ny = y + (map[x][y] * py[i]);

if (nx >= 0 && ny >= 0 && nx < N && ny < N) 

dp[x][y] += dfs(nx, ny);

}

return dp[x][y];

}

int main(){

cin >> N;

for (int i = 0; i <N; i++){

for (int j = 0; j <N; j++){

cin >> map[i][j];

dp[i][j] = -1;

}

}

cout << dfs(0, 0) << endl;

system("pause");

return 0;

}