동전교환(DFS)

코드

  function solution(m, arr) {
    let answer = Number.MAX_SAFE_INTEGER;
    let n = arr.length;

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

    DFS(0, 0);
    return answer;
  }

풀이

이 문제는 DFS(L, sum)으로 해서 풀어야한다. 여기서 L은 동전의 개수이고 sum은 값의 합이다. 

위 사진처럼 가지를 뻗어 가면서 돌아가도록 해야한다. 그러다가 sum이 거스름 돈보다 크거나 L이 answer보다 커지면 가지 뻗는 것일 종료해야 한다. 이를 구현한 것이 위 코드이다.