최대 배열의 크기가 1002, 1002이기 때문에 백트랙킹으로는 문제를 해결할 수 없다.
tmp[2][1002] 배열은 좌측에서 오는 값을 기록, 우측에서 오는 값을 기록하는 배열이다.
이런 방식으로도 메모제이션을 진행할 수 있다는,, 잘 기억해두자!!
Code
Fealing
그래프 탐색 중독자인가보다. 좌 우 아래를 탐색한다는 것을 보고, 백트랙킹으로 문제를 풀어버렸다.
근데 1002, 1002면 시간초과가 당연히 날 수 밖에 없는데, 고집부리고 백트랙킹으로 해결한 것 같다.
좌측에서 오는 값, 우측에서 오는 값을 기록해놓는 배열을 하나 더 두면 쉽게 해결할 수 있는 문제였다.
다음에도 이런 문제가 나왔으면 좋겠다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.