동전교환

문제

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

제한사항

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

입출력 예

풀이

function solution2(m, arr) {
  let arrSort = arr.sort((a, b) => b - a);
  console.log(arrSort);
  let money = m;
  let count = 0;
  for (let x of arrSort) {
    if (x <= money) {
      count += Math.floor(money / x);
      money = money - Math.floor(money / x) * x;
    }
  }
  return count;
}
console.log(solution2(15, arr));

• 대표적인 그리디 문제 중 하나.
• 동전을 내림차순으로 정렬하면 쉽게 해결할 수 있다.

function solution(m, arr) {
  arr.sort((a, b) => a - b);
  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이 코인의 갯수가 된다. 직관적으로 이해가 되진 않지만 자세히 들여다보면 이해가 금방 될 것이다. 꾸준히 코드를 읽어보자.