juhongkim2   6년 전

두 코드 모두 메모이제이션을 이용한 재귀함수로 짰습니다.

ac코드는 d배열을 모두 -1로 초기화했고 시간초과나는 코드는 d배열을 그냥 0인 상태로 뒀습니다.


어떤차이가 있는건가요?


아 시간초과코드도 재채점 전에는 4ms로 ac나오던 코드였습니다...

어떤케이스가 추가된거길래...

sosfd   6년 전

덕분에 해결했습니다. 감사합니다. 아마도 dp[i][j]를 0으로 두면 dp[i][j] 에서 (N,M) 까지 가는 경로가 없을 경우에도 다시 재귀를 도니깐 그런것같습니다. -1로 둘시에 (N,M) 으로 가는 경로가 없으면 dp[i][j]는 0으로 되고 다시 (i,j)로 왔을때 0을 바로 리턴해줄테니깐요

yukariko   6년 전

내리막길을 타다보면 경로에따라 멈추는 지점이 존재합니다.
그 지점에서의 dp값은 0이 됩니다.
그러면 dp 배열의 초기값과 같기때문에 다시 그 지점에 왔을때 연산을 다시수행하게 됩니다.
이런것들이 쌓이면 시간초과가 발생할 수 있습니다.
-1로 초기화하게되면 0을 처리할 수 있어서 이런 문제점이 해결됩니다.

juhongkim2   6년 전

허... 이건 미처 생각도 못한부분이네요 덕분에 완전히 해결되었습니다.
두분 모두 정말감사합니다!

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