최소 동전 교환 문제

•정의

주어진 금액을 동전 d₁,d₂,...,d𝐧으로 바꿔줄 때 필요한 동전의 최소 개수를 찾는 문제.
목적은 금액n을 나타내는 동전의 조합 중 개수를 최소로 하는 경우를 찾는 것.

•코드

class MinCoinChange {
  constructor(coins){
    let items = coins; // 동전 금액에 해당하는 값을 배열 인자로 받는다.
    let cache = {}; // 중복 계산을 최대한 피하고 효율적인 실향을 위해
    this.makeChange = amount => {
      let me = this;
      if(!amount){
        return []; // 금액이 음수라면 빈 배열을 반환
      }
      if(cache[amount]){ // 이미 캐시되어 있다면 캐시값을 그냥 반환하고 캐시 전이라면 이후 코드 실행
        return cache[amount];
      }
      let min = [], newMin, newAmount;
      for(let i = 0; i < items.length; i++){ // 각 동전에 대해
        let coin = items[i];
        newAmount = amount - coin; // newAmount 계산, 교환 가능한 최소 금액에 도달할 때 까지 계속 줄어들 것이다.
        if(newAmount >= 0){
          newMin = me.makeChange(new Amount); // 유효한(양수인) newAmount 값에 대해 다시 재귀호출하여 결과를 담는다.
        }
        if(newAmount >=0 && // newAmount 값이 유효한지
          (newMin.length <min.length-1 || !min.length)&& // 최적의 newMin이 도출 됐는지
          (newMin.length || !newAmount)){ // newMin과 newAmount 모두 유효한 값인지
          min = [coin].concat(newMin); // 모두 충족한다면 이전보다 더 나은 결과를 얻었다는 반증
        }
      }
      return (cache[amount] = min); // 최종결과 반환
    }
  }
}