동전교환

문제풀이

재귀함수를 DFS(L)이라고 할때 끝나는 층(L)이 각각의 경우마다 다르다.
그러므로 재귀함수가 끝나는 기준은 거슬러줄 동전의 합(sum)을 기준으로 해야 한다.

function solution(m, arr){      
        let answer = Number.MAX_SAFE_INTEGER;         
        function DFS(L, sum) {
            if(sum>m) return;
            if(L >=answer) return;
            if(sum === m) {
                answer = Math.min(answer, L);   
                console.log(answer);                                         
            }
            else {
                for(let i =0; i<arr.length; i++){                                                        
                    DFS(L+1, sum + arr[i])
                }
            }
        }
        DFS(0,0);
        return answer;
    }
    let arr=[1, 2, 5];
    console.log(solution(15, arr));

• sum = m 일때의 동전갯수만 유효하다.
  -> sum > m 은 조건에 맞지 않으므로 return해준다.
• answer는 조건에 부합하는 가장 작은 수이므로 만약 L이 answer보다 재귀함수의 끝까지 갈 필요가 없으므로 return해준다.