점프 (feat. 백준, 1890번)

점프
https://www.acmicpc.net/problem/1890

1890번: 점프

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1890
#include <iostream>
using namespace std;
int N;
long long dp[101][101];
char arr[101][101];
long long solution(register int x, register int y) {
	if (x == N && y == N)
		return 1;
	if (arr[x][y] == 0)		return 0;
	if (dp[x][y] > 0)		return dp[x][y];
	register char t = arr[x][y];
	if (x + t <= N)
		dp[x][y] += solution(x + t, y);
	if (y + t <= N)
		dp[x][y] += solution(x, y + t);
	return dp[x][y];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> arr[i][j], arr[i][j] -= '0', dp[i][j] = 0;
	cout << solution(1, 1) << "\n";
	return 0;
}
// *&)*@*

"내리막 길" 이라는 문제와 문제 자체는 다르지만 접근 방법은 상당히 비슷합니다. 같이 풀어보시길 권장합니다.

내리막 길 (feat. 백준, 1520번)

1. 하나의 길에 대해서 완료할때, 거치는 노드에 대해서 도착하는 경우의 수를 모두 기록합니다.
2. 이후 다른 길로 시작되더라도 동일한 노드를 거친다면, 도착점까지 가는게 아니라 그 노드에 기록된 경우의 수만을 가져오는 방식입니다.