JUMPGAME 이란 문젠대







아래는 내가 쓴 코드야...


동적계획법이란걸 공부했고 그걸 활용해서 해봤어... 근데 결과는 시간초과... 하 ...


적절한 코멘트좀 달아줄수 있남 ㅎㅎ  뭣때메 시간초과가 나오는지 이해가 잘 안가네 ...


#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
int num;
int arr[100][100];
int cache[100][100];
int jump(int x, int y);

int main(void)
{

int te1st1Case; //test라고 치면 디씨에 글이 안올려져서 te1st1Case라고 한것 scanf("%d", &te1st1Case); while (te1st1Case) { te1st1Case--; scanf("%d", &num); memset(arr, 0, sizeof(arr)); memset(cache, 0, 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] != 0) return cache[x][y]; int jumpSize = arr[x][y]; return cache[x][y] = (jump(x + jumpSize, y) || jump(x, y + jumpSize));

}