Memoization1 [BOJ] 1937. 욕심쟁이 판다(Python) / DFS + DP 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 처음 이 문제를 DFS 각 위치별 완전탐색으로 접근했더니 답은 금방 구했지만, 바로.. 시간초과가 떴다.. 아니나 다를까 DFS + DP의 콜라보로 풀어야 하는 문제였다. 즉, Memoization을 해야한다는 것! Memoization은 이미 한 번 탐색한 위치에 대해서는 재귀로 더 탐색할 필요 없이 그냥 그 값을 가져다 사용할 수 있도록 해당 위치별 값을 미리 저장한 DP Table을 만들어두는 것이 포인트다! 즉, 불필요한 반복 연산 없이 한 번 .. 2021. 4. 1. 이전 1 다음
