[백준] 알고리즘 1890번 - 점프 문제

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

1890번: 점프

소스코드

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[101][101];
long long dp[101][101];
long long dfs(int x, int y) {
	if (x == n-1 && y == n-1) return 1;
	else if (dp[x][y] == -1) {
		dp[x][y] = 0;
		// 오른쪽가는친구
		int right_x = x+ arr[x][y];
		int right_y = y;
		if (right_x >= 0 && right_x < n && right_y >= 0 && right_y < n) {
			dp[x][y] += dfs(right_x, right_y);
		}
		int down_x = x;
		int down_y = y + arr[x][y];
		if (down_x >= 0 && down_x < n && down_y >= 0 && down_y < n) {
			dp[x][y]+=dfs(down_x, down_y);
		}
	}
	return dp[x][y];
}

int main() {
	ios_base::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;
		}
	}
	cout<<dfs(0, 0);
}
 

풀이

DFS와 DP를 같이 이용하여 해결할 수 있는 문제입니다.

이건 저도 해설을 봐서 풀었는데, 좀 더 공부한 후에 수정하겠습니다.