안녕하세요.
맨 처음 그저 재귀로만 백트래킹 하다가..
시간초과가 나서 메모이제이션을 사용하고, memset함수로
캐시배열을 초기화 하였는데도 시간초과가 났습니다.
그래서 인풋을 받을 때 캐시도 같이 초기화를 해주었는데도
시간초과가 뜨네요..
문제점이 무엇인지 알 수 있을까요?
아래는 제 소스입니다.
#include<stdio.h>
int map[105][105], memo[105][105];
int n;
int jump(int i, int j)
{
if(i >= n || j >= n)
return false;
if(i == n-1 && j == n-1)
return true;
int t = memo[i][j];
if(t > 0)
return t;
int size = map[i][j];
return t = jump(i+size, j) || jump(i, j+size);
}
int main()
{
int testcase;
scanf("%d", &testcase);
while(testcase--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &map[i][j]);
memo[i][j] = 0;
}
}
printf("%s\n", jump(0, 0) ? "YES" : "NO");
}
}
박다은
안녕하세요.
맨 처음 그저 재귀로만 백트래킹 하다가..
시간초과가 나서 메모이제이션을 사용하고, memset함수로
캐시배열을 초기화 하였는데도 시간초과가 났습니다.
그래서 인풋을 받을 때 캐시도 같이 초기화를 해주었는데도
시간초과가 뜨네요..
문제점이 무엇인지 알 수 있을까요?
아래는 제 소스입니다.
11년 전