1. 거스름 돈 계산

이번엔 거스름 돈을 줄때 동전 갯수가 최소가 되게 하면 된다. changes = 15,coins = [1,2,5] 가 주어졌을 때 1,2,5의 조합으로 15가 되게 합을 만들어야 한다. 이때 동전의 갯수가 최소한으로 되게 하고 그때의 갯수를 return하면 된다.

2. 접근방법

우선 부분 집합을 만들어야 하는데 이때 coins에서 하나의 원소가 수십번 뽑힐 수 도 있다. 15가 되기 전까지는 말이다.
이때 뽑히는 횟수를 level로 보고 level이 깊어지면서 부분집합이 만들어지는데 이 부분집합의 합을 sum이라고 하자.

또한 여기서 한 걸음 더 나아가 최소한의 동전의 갯수를 뽑았을때 무엇을 뽑았는지도 알아보도록하자.

• pseudoCode
  • dfs를 만들어주고 안에 (0,0) 을 pass한다. parameter는 (level(동전갯수),sum(그때의 동전의 합)) 을 의미한다
  • dfs에 level을 추가하고 sum에다가 현재 동전의 조합을 더하여 pass한다.(sum을 누적해서 pass하는 방법이다)
  • 그리고 sum > changes || 현재 구한 최소동전의 갯수가 갱신된 최소갯수보다 크면 return
  • sum === changes라면 answer에다가 현재sum일때 갯수와 기존 answer와 비교한다음 적은것을 할당
  • 각 sum에서 조합을 구하는 법
    • for문을 만들고 안에다가 coinComb[level] = coins[i] 라고 하면 dfs재귀가 호출될때마다 동전의 조합이 만들어질 것이다
    • dfs가 끝나면 ch를 풀어야 할 것이다.

그럼 이제 구현해보자!

function showCoins(changes, coins) {
  // 코인의 가장 작은 값으로 changes를 나누는게 가장 갯수가 많으므로. 최대 갯수를 구해주는 과정
  let coinComb = Array.from({ length: changes / coins[0] }, () => 0);
  let answerComb;

  let answer = Number.MAX_SAFE_INTEGER;

  function dfs(level, sum) {
    if (sum > changes || level >= answer) return;
    if (sum === changes) {
      answer = Math.min(level, answer);
      answerComb = coinComb.slice();
    } else {
      for (let i = 0; i < coins.length; i++) {
        coinComb[level] = coins[i];
        dfs(level + 1, sum + coins[i]);
        coinComb[level] = 0;
      }
    }
  }

  dfs(0, 0);
  return { answer, answerComb };
}

showCoins(3, [1, 2, 5]);
// answer: 3
// answerComb: (16) [0, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]