처음에 2차원 배열로 캐시값을 구현했더니, 메모리 초과가 나서,

낭비되는 공간이 많은 것 같아서 DP 를 map 을 써서 구현했습니다.

map 은 이진 탐색 트리라 탐색속도가 빠른 것 같은데 어느 부분에서 시간초과가 나는 걸까요?

점화식은 D[K][F] = K를 만드는 경우의 수 (F는 사용한 가장 큰 동전의 인덱스)

동전은 coin 변수에 가장 큰 값부터 역순으로 저장을 해놨습니다.

그래서 본문 예제처럼 K 가 10이고, 동전의 갯수는 3개 1 ,2, 5 일때

coin[0]=5,coin[1]=2,coin[2]=1 이 되고

구하고자 하는 D[10][0] 은 

D[5][0] , D[5][1] , D[5][2] 이런식으로 분할됩니다.

D[5][0] 는 5 5 , 5 2 2 1 , 5 2 1 1 1 , 5 1 1 1 1 1 이런값이 들어가고

D[5][1] 에는 2 2 2 2 2 , 2 2 2 2 1 1 , 2 2 2 1 1 1 1, 2 2 1 1 1 1 1 1 , 2 1 1 1 1 1 1 1 1

D[5][2] 에는 1 1 1 1 1 1 1 1 1 1 

이런식으로 들어가는 점화식입니다.

72%정도가서 시간초과 에러가 뜨는데... 어떤 문제인지 궁금합니다.

map 이 배열보다 속도가 느린건 알지만...

이래서 DP 에서 map 을 안 쓰는건가요??

추가적으로... 이게 안된다면 이 문제는 재귀적으로 풀 방법이 없나요..?

아무리 뒤져도 재귀로 푸신분들은 안보이고..

풀려면 이차원으로 풀어야 할 것같은데..메모리초과가 나고...ㅠㅠ