알고스팟 - 외발 뛰기 (JUMPGAME) [C++]

 이 문제는 다이나믹 프로그래밍으로 간단하게 해결할 수 있다. 이 문제에서 격자의 최대 크기는 100 x 100 이고, 각 칸에서 오른쪽이나 아래를 선택해야 한다. 따라서 완전 탐색으로는 O(2^10000) 이므로 절대 시간 안에 풀 수 없다. 그러나 다이나믹 프로그래밍을 사용하면 이미 있는 (y, x) 결과에 대해서 바로 리턴하므로 dp 배열을 다 채우는 시간만큼만 연산을 수행하게 된다. 따라서 O(n^2) 이 되고, 시간 안에 충분히 풀 수 있게 된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100

int matrix[MAX][MAX];
int n;

int dp[MAX][MAX];

void init() {
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			dp[y][x] = -1;
		}
	}
}

bool inRange(int y, int x) {
	if (0 <= y && y < n && 0 <= x && x < n) {
		return true;
	}
	return false;
}

int solve(int y, int x) {
	if (y == n - 1 && x == n - 1) {
		return 1;
	}

	if (dp[y][x] != -1) {
		return dp[y][x];
	}

	int result = 0;

	// right
	if (inRange(y, x + matrix[y][x])) {
		result = max(result, solve(y, x + matrix[y][x]));
	}

	// down
	if (inRange(y + matrix[y][x], x)) {
		result = max(result, solve(y + matrix[y][x], x));
	}

	return dp[y][x] = result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		cin >> n;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				cin >> matrix[y][x];
			}
		}
		init();

		int result = solve(0, 0);

		if (result) {
			cout << "YES" << '\n';
			continue;
		}
		cout << "NO" << '\n';
	}

	return 0;
}