[알고리즘/인프런] 동전교환

문제 

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

 

풀이

L은 각 동전을 사용할 때마다 1씩 증가하므로 사용된 동전의 개수와 동일하다. 또한 최소 개수가 구해진 상태에서 해당 L보다 더 깊이 탐색할 필요가 없기 때문에 L >= minCoinCnt인 경우는 바로 리턴한다.(Edge cutting)

function solution(change, arr) {
  let minCoinCnt = Number.MAX_SAFE_INTEGER;
  const n = arr.length;

  function DFS(L, sum) {
    if (L >= minCoinCnt) return;
    if (sum > change) return;
    
    if (sum === change) {
      minCoinCnt = Math.min(minCoinCnt, L);
    } else {
      for (let i = 0; i < n; i++) {
        DFS(L + 1, sum + arr[i]);
      }
    }
  }

  DFS(0, 0);
  return minCoinCnt;
}