개발뚱땅

동적계획법으로 풀었다.

memset에서 초기화 해줄 때 크기에 자료형 크기만큼 해주지 않아 초기에 오답이 발생했다.

메모이제이션.

base case 초기에 넣어주고 이미 기록 되어있는지 확인. 그 위치에 간 기록이 있고 결과가 있는지.

있다면 바로 반환, 없다면 계산을 하기위해 다시 문제를 작은문제로 분할.

아래로 가는경우와 오른쪽으로 가는 경우.

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

#include <bits/stdc++.h>

using namespace std;

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

int sol(int x, int y, int size){
	if(x>=size || y>=size){
		//넘침 
		return 0;
	}
	if(x == size-1 && y == size -1){
//		도착 
		return 1;
	} 
	
	if(cache[x][y] != -1){
		return cache[x][y];
	} 
	int jum = board[x][y];
	int &ret = cache[x][y];
	//오른쪽으로 가능 경우
	return ret = max(sol(x+jum, y, size), sol(x, y+jum, size));
	//아래로 가는 경우 
}

int main(){
  int n;
  cin>>n;
  for(int _times = 0; _times < n; ++_times)
  {
  	memset(cache, -1, 10000*sizeof(int));
	int _size;
	cin>>_size;
	for(int i=0; i<_size; ++i){
	  for(int j=0; j<_size; ++j){
		cin>>board[i][j];
	  }
	}
	if(sol(0, 0, _size)==1){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
  }
 return 0;
}