(BOJ) 1890 점프

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

 

문제풀이:

"경로의 개수는 2^63-1보다 작거나 같다." -> long long 

"메모리 제한: 128 MB" -> DP

 

이미 갔던 길 다시 안가고 그 지점에서 갈 수 있는 경우의 수+1 해주면 됨

 

* 함수 리턴 타입 확인 잘하자....  int func()해서 계속 틀림 ㅠㅅㅠ

 

소스코드:

int n, arr[100][100];
long long dp[100][100];

long long func(int x, int y) {
	if (x == n - 1 && y == n - 1) return 1;
	if (x >= n || y >= n) return 0;
	long long& ret = dp[x][y];
	if (ret != -1) return ret;
	ret = 0;
	return ret = func(x + arr[x][y], y) + func(x, y + arr[x][y]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	func(0, 0);
	cout << dp[0][0] << '\n';
	return 0;
}