백준 1890번: 점프

[문제 링크]

1890번: 점프

---

https://onlytrying.tistory.com/102

내리막길 문제와 비슷한 유형의 문제였다.

(y,x)에서 (N,N)으로 가는 경우의 개수는 항상 같기 때문에 이를 메모이제이션 하면 중복을 최소화할 수 있다.

---

#include <iostream>
#include <cstring>
using namespace std;

int N, arr[101][101];
long long memo[101][101];
int dy[2] = { 0, 1 }, dx[2] = { 1, 0 };

long long Topdown(int hereY, int hereX)
{
	if (hereY == N && hereX == N) return 1;
	if (arr[hereY][hereX] == 0) return 0;

	long long& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	int jump = arr[hereY][hereX];
	for (int i = 0; i < 2; i++)
	{
		int nextY = hereY + (dy[i] * jump);
		int nextX = hereX + (dx[i] * jump);

		if (nextY <= N && nextX <= N)
			ret += Topdown(nextY, nextX);
	}

	return ret;
}

long long Bottomup()
{
	memo[1][1] = 1;

	for(int i = 1; i<=N; i++)
		for (int j = 1; j <= N; j++)
		{
			if (arr[i][j] == 0)
				continue;

			if (i + arr[i][j] <= N)
				memo[i + arr[i][j]][j] += memo[i][j];

			if (j + arr[i][j] <= N)
				memo[i][j + arr[i][j]] += memo[i][j];
		}

	return memo[N][N];
}

int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> arr[i][j];

	memset(memo, -1, sizeof(memo));
	cout << Topdown(1, 1) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 89 day