[DP&DFS] 백준 1890 점프

www.acmicpc.net/problem/1890

1890번: 점프

수행 시간: 1시간

처음 도전해본 DP 문제! 요즘 친구와 타임어택으로 문제를 풀고 있는데, 수월하게 풀다가 마지막에 제출하는 과정에서 오류가 떠서 친구에게 답을 구했는데, 2의 63승 만큼의 메모리가 필요하므로 DP배열을 int형(4byte이므로 32bit 즉, 2의 32승)이 아닌 long long 형 (8 byte이므로 64bit 즉, 2의 64승) 으로 자료형을 바꿔줘야 했다.

#include <iostream>
#include <vector>
using namespace std;
int n;
int map[102][102];
long long dp[102][102];
int check = -1;

long long graph(int x, int y) {
	if (x == n - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] > check) {
		return dp[x][y];
	}
	else if (dp[x][y] == check) {
		dp[x][y] = 0;
		//오른쪽으로 점프
		int rx = map[x][y] + x;
		int ry = y;
		if (rx >= 0 && rx < n && ry >= 0 && ry < n) { //조건 만족
			dp[x][y] += graph(rx, ry);
		}
		//아래로 점프
		int dx = x;
		int dy = map[x][y] + y;
		if (dx >= 0 && dx < n && dy >= 0 && dy < n) { //조건 만족
			dp[x][y] += graph(dx, dy);
		}
	}
	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] = check;
		}
	}
	cout << graph(0, 0);
}