강의로 돌아가기
이관구

효율성 뭐가 문제일까요?

include

include

include

include

using namespace std;

vector> cache(101,vector(101,-1));
vector> cache2(101,vector(101,-1));
bool ispuddles(int x,int y,vector> puddles)
{
int& ref = cache2[y][x];
if(ref!=-1)
return static_cast(ref);

for(int i=0;i<puddles.size();i++)
{
if(puddles[i][0]-1==x && puddles[i][1]-1==y)
{
ref=1;
return true;
}
}

ref=0;
return false;
}
int recursive(int m,int n,vector> puddles,int startx,int starty)
{

if(m==1 && n==1)
return 1;

int& ref=cache[n][m];

if(ref!=-1)
return ref;

int temproot=0;

if(!ispuddles(startx+1,starty,puddles)&&m-1>=1)
temproot=recursive(m-1,n,puddles,startx+1,starty);

if(!ispuddles(startx,starty+1,puddles)&&n-1>=1)
temproot+=recursive(m,n-1,puddles,startx,starty+1);
temproot%=1000000007;
ref = max(ref,temproot);

return ref;

}

int solution(int m, int n, vector> puddles)
{

int answer = 0;

answer= recursive(m,n,puddles,0,0);

return answer;
}

캐시를 2개썼는데도 안나오네요

첫번째 캐시는 사이즈 [m,n]인곳으로 갈 수 있는 최단거리 갯수고요
두번째 캐시는 그 지점이 물에 침수된곳인지를 나타냅니다

정확성은 되었는데 뭐가 문제일까요

1 개의 답변
정성환

효율성테스트에 경우 최단거리의 갯수가 int값을 넘어가능 경우가 생기기 때문에 각 지점까지의 최단거리를 구할때마다 1000000007로 나누는 방식으로 구하셔야 합니다

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.