cesta123   5년 전

질문들을 검색해보았구요.

다만 memoization을 -1로 초기화 한 경우에는 아예 답이 음수로 틀리게 나오게 되고(d[x][y]에 계속 더해져서 그런거 같구요. if(d[x][y] != -1)로 했었습니다.)
밑에 있는 코드로 하게되면 시간초과가 나오게 됩니다. 질문을 봤더니 갈 수 없는 경우에 계속 재귀하게 되는 현상인 거 같았는데요.

의아한 것은 1520 강의자료에 있는 top-down방식 정답코드를 돌려도 틀리다고 나오네요.

더이상 해결해볼 방법이 없어서 질문 올립니다.. 다만 지금 방식이 답으로 나오는 거 같긴한데 시간초과 문제점이 있고,
또한 반례에서 더이상 갈수 없는 경우에 0을 리턴해버리면 0이 나올 수 밖에 없었구요. 해결 방법을 모르겠습니다. 도와주세요 ㅜ.
또한 scanf, printf로 바꿔봐도 똑같이 19퍼센트 지점에서 시간초과가 나서 cin, cout문제는 아닙니다.

Green55   5년 전

0을 초기값으로 두면, d[x][y] = 0일 때 이게 처음 방문 해서 0인건지, 아니면 경로의 개수가 0이어서 0인건지 구별이 안되기 때문에 이 부분문제를 계속해서 풀기 때문에 시간 초과가 날 수 밖에 없습니다. 초기값은 반드시 답으로 절대 나올 수 없는 값으로 해야 효과가 있습니다.

현재 코드에서 34라인 살리시고, 17라인에 d[x][y] = 0 넣으시면 AC 뜹니다.

cesta123   5년 전

아 x,y 방문하면서 0으로 표시해줘야 하는건데.. 실력이 너무 부족하다보니..ㅎㅎ 답변 정말 감사합니다.

혹시 답변 보시는 분들을 위해,

16번 째 if(d[x][y] != -1) return d[x][y];
17번 째 d[x][y] = 0; 추가
34번 째 memset(d, -1, sizeof(d));

로 사용하시면 정답 문제 없이 나옵니다~!

cesta123   5년 전

아 그리고 dp 쓸 때 답 사용에 대한 조언 너무 감사합니다.

댓글을 작성하려면 로그인해야 합니다.