ACM - RPG

링크: https://www.acmicpc.net/problem/1315

Dynamic Programming이 핵심입니다.

memoizaiton을 사용하여 힘, 지능 [1001][1001] 배열 3개를 사용하였습니다.

두 가지 memoization cache 배열을 사용하여 누적 포인트에 대한 cache 와 성공횟수에 대한 cache를 만들었습니다. (pnt_cache, success_cache)

남은 한 개의 cache 배열(res_cache)은 재귀를 사용하여 DFS 방식으로 (힘, 지능)을 순회하며 기록하기 위한 배열입니다. 같은 곳을 호출한다면 더 내려가지 않고 바로 반환할 수 있게 하기 위해서 입니다.

※ 더 최적화 할 수 있는 방법
pnt_cache, success_cache 두 배열을 출력해보면 누적 포인트 변화와 성공 횟수에 따른 변화점이 같다. 이 성질을 이용하면 res_cache와 DFS 재귀 방식을 사용하지 않고 답을 구할 수 있을 것 같다. loop를 1000*1000*100번 만으로 끝낼 수도 있을 것이다.