cache를 활용한 이유가 중복이 발생하지 않음인데

cache를 전혀 활용하지 못했었어

고마워  



#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <string.h>

int num;

int arr[100][100];

int cache[100][100];

int jump(int x, int y);


int main(void)

{


int t1estCase;


scanf("%d", &t1estCase);


while (t1estCase)

{

t1estCase--;


scanf("%d", &num);

memset(arr, 0, sizeof(arr));

memset(cache, -1, sizeof(cache));


for (int i = 0; i < num; i++)

for (int j = 0; j < num; j++)

scanf("%d", &arr[i][j]);


if (jump(0, 0))

printf("Yes\n");

else

printf("No\n");

}


return 0;

}


int jump(int x, int y)

{

if (x >= num || y >= num)

return 0;


if (x == num - 1 && y == num - 1)

return 1;



if (cache[x][y] != -1)

return cache[x][y];

int jumpSize = arr[x][y];

return cache[x][y] =  (jump(x + jumpSize, y) || jump(x, y + jumpSize));



}