[DFS-Cut Edge]동전교환

문제

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

 

문제풀이

트리 DFS

 

코드

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

  function DFS(L, sum) {
    if(sum > m) 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;
}

const arr = [1, 2, 5];
console.log(solution(arr, 15));

 

DFS-Cut Edge

위 코드만으로도 동전의 가장 적은 수를 구할 수 있지만 다음과 같은 문제가 있다.거스름돈이 되는 경우의 수를 콘솔 창에서 확인한 결과,

결과 출력

동전 종류의 갯수가 5개일 경우 이보다 더 많은 동전 종류를 사용해서 거스름돈과 같은 금액을 산출하는 작업은 현재 가장 적은 수의 동전으로 교환해야 하는 이 문제에서 불필요하다.이러한 불필요한 작업을 생략하기 위해서는 현재까지 동전 종류의 갯수를 저장하고 있는 변수보다 현재 레벨 값(새롭게 구하는 경우의 수)이 크거나 작을 경우 재귀를 종료하면 된다.

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

  function DFS(L, sum) {
    if(answer <= L) return; //Cut Edge
    if(sum > m) 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;
}

const arr = [1, 2, 5];
console.log(solution(arr, 15));