동적 계획법 - 1. 외발 뛰기

문제 : 외발 뛰기 (난이도 下)

 

https://algospot.com/judge/problem/read/JUMPGAME

 분석

방향이 오른쪽 아님 아래쪽이기에 재귀함수로 구현이 쉽다.

그러나 모든 칸의 수가 같은 경우 시관이 초과해 버린다.

 

하지만 앞서 배운 Memoization(메모이제이션)을 이용하면 간단히 해결할 수 있다.

2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

 

 구현

int cache[100][100];
bool jump(const vector<vector<int>>& board, int y, int x, int n)
{
	//base case: 보드판을 나간 경우. 
	if (x >= n || y >= n) return false;
	//base case: 마지막 칸인 경우
	if (y == n - 1 && x == n - 1) return true;
	//memoization
	int& ret = cache[y][x];
	int jump_data = board[y][x];
	if (ret != -1)
	{
		return ret;
	}
	return ret = (jump(board, y + jump_data, x, n) || jump(board, y, x + jump_data, n));
}


int main()
{
	int C;
	cin >> C;
	while (C--)
	{
		int n;
		cin >> n;
		vector<vector<int>> board(n, vector<int>(n));
		memset(cache, -1, sizeof(cache));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> board[i][j];
			}
		}

		if (jump(board,0,0,n))
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';
		}
	}
	return 0;
}