[C/C++] 알고스팟 - 외발 뛰기

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

algospot.com :: JUMPGAME

 

메모제이션 기법을 통해서만 해결 가능한 문제

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define MAX_SIZE 101
#define swap(type,x,y) do{type t=x; x=y;y=t;} while(0)

using namespace std;

int N;
int adj[MAX_SIZE][MAX_SIZE];
int graph[MAX_SIZE][MAX_SIZE];

int isPossible(int y, int x) {
	if (y >= N || x >= N) return 0;
	if (y == N - 1 && x == N - 1) return 1;
	if (adj[y][x] != -1) return adj[y][x];
	int jump = graph[y][x];
	return adj[y][x] = (isPossible(y + jump, x) || isPossible(y, x + jump));
}

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

	int test_case;
	cin >> test_case;
	
	while (test_case--) {
		cin >> N;
		memset(adj, -1, sizeof(adj));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> graph[i][j];
			}
		}
		if (isPossible(0,0)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}