[알고스팟][C++] JUMPGAME: 외발 뛰기

문제 링크: https://algospot.com/judge/problem/read/JUMPGAME

 

n*n 크기의 격자에 1~9까지 정수를 쓴 게임판이 있습니다. 맨 왼쪽 위부터 시작해서 각 칸에 적혀있는 수만큼 오른쪽 또는 아래쪽으로 이동할 수 있습니다. 이때 시작점에서 끝점까지 도달하는 방법이 존재하는지 찾는 것이 목적입니다.

점화식을 만들어봅시다.

\[jump(y,x)=\text{(y, x)에서부터 맨 마지막 칸까지 도달할 수 있는지 여부를 반환}\]

오른쪽, 아래 둘 중 하나만 성공해도 상관 없으니 다음과 같이 재귀적으로 표현할 수 있습니다.

\[jump(y,x)=jump(y+jumpSize,x)~||~jump(y,x+jumpSize)\]

메모이제이션을 적용하면 완료입니다.

#include <bits/stdc++.h>
using namespace std;


int n;
int board[100][100];
int cache[100][100];

bool solve(int y, int x) {
	if (y < 0 || y >= n || x < 0 || x >= n) return false;
	if (y == n - 1 && x == n - 1) return true;

	auto& ret = cache[y][x];
	if (ret != -1) return ret;
	auto jump_size = board[y][x];
	return ret = solve(y+jump_size, x) || solve(y, x+jump_size);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		memset(cache, -1, sizeof(cache));
		cin >> n;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				cin >> board[i][j];

		cout << (solve(0, 0) ? "YES\n" : "NO\n");
	}

	return 0;
}

cache 배열은 사실상 0, 1의 정수만 반환하지만 초기화되었는지 아닌지 여부를 저장하기 위해 -1로 초기화되어야 합니다. 그래서 int 자료형을 사용합니다.