[JavaScript/section 8] 09 - 동전교환

📌 09 - 동전교환(DFS)

여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려고 한다. 이때 동전의 최소 개수를 출력하는 문제이다. 각 단위의 동전은 무한정 쓸 수 있다.

입력예제
1 2 5
15
출력예제
3

설명: 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

👍 풀이 방법

중복순열 구하기 문제를 먼저 이해하고 온다면 어렵지 않게 이번 문제를 해결할 수 있을 것이다. 단, 이번에는 함수를 종료시켜야 하는 시점을 잘 생각해봐야 한다. 불필요한 탐색까지 할 필요가 없기 때문이다.

• 동전의 최소 개수를 구하는 문제이므로 answer(그 시점에 동전의 최소 개수)보다 L(레벨, 동전의 개수)이 크거나 같다면 더 이상 깊이 탐색할 필요 없이 return 한다.
• sum(동전의 합)이 m(거스름돈)을 초과한다면 return 한다.

function solution(m, arr) {
  let answer = Number.MAX_SAFE_INTEGER;
  let n = arr.length;
  let arrCopy = Array.from(arr).sort((a, b) => b - a);

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

let arr = [1, 2];
console.log(solution(4, arr));