[1890] 점프

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

1890번: 점프

 

접근:

• 기저 사례는 총 세 개로, (N-1,N-1)을 밟는 경우 / 범위를 넘어가는 경우 / 중간 단계에서 0을 밟는 경우 이다.
• 기저 사례는 (N-1,N-1)을 밟는 경우 -> 범위를 넘어간는 경우 -> 중간 단계에서 0을 밟는 경우 순서대로 처리한다.
• y,x를 받아 N,M까지 가는 경우의 수를 반환하는 형태의 재귀 + bottom up 방식으로 DP 함수를 구현했다.
• 경우의 수가 2^63-1까지 가므로, int 자료형이 아니라 long long 자료형을 사용했다.

 

코드:

#include <iostream>
#include <memory.h>

using namespace std;

typedef long long dl;
int N;
int map[101][101];
dl cache[100][100];

dl findPath(int y, int x)
{
	if (y == N - 1 && x == N - 1) return 1;
	if (y >= N || x >= N) return 0;
	if (!map[y][x]) return 0;
	
	dl& ret = cache[y][x];
	if (ret != -1) { return ret; }

	return ret = findPath(y, x + map[y][x]) + findPath(y + map[y][x], x);
}

int main()
{
	ios::sync_with_stdio(false);
	memset(cache, -1, sizeof(cache));

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	cout << findPath(0, 0) << "\n";

	return 0;
}