잔돈 만들기

문제

50센트, 25센트, 10센트, 1센트 동전으로 1달러 만큼의 잔돈을 만드는 방법

 

일반화

여러 종류의 동전들로 임의의 금액을 조합하는 방법의 수

 

재귀적 함수 풀이

사용가능한 동전 종류들이 일정한 순서로 배열되어 있을 때, 아래 관계 성립

- n 가지 동전들 이용해서 금액 a를 만드는 방법 수

-- 첫 번째 종류의 동전을 제외한 나머지 동전들로 금액 a를 만드는 방법 수

-- n가지 종류의 동전을 모두 사용해서 금액 a-d를 만드는 방법의 수

---- d: 첫 번째  종류 동전의 액면가

 

풀이 방향

"여러 가지 동전들로 주어진 금액을 만드는 방법의 수를 구하는 문제"는 "더 적은 금액을 만드는 문제 또는 더 적은 수의 동전으로 금액을 만드는 문제"와 같다. 따라서 아래 조건을 만족하는 재귀적 알고리즘을 구현해본다.

 

재귀적 알고리즘의 조건

- 만일 a가 정확히 0이면 잔돈을 만드는 방법은 단 한 가지이다.

- 만일 a가 0보다 작으면 잔돈을 만드는 방법은 0가지 이다.

- 만일 n(동전 종류)이 0이면 잔돈을 만드는 방법은 0가지 이다.

 

     function count_change(amount) {
        return cc(amount, 5);
      }

      function cc(amount, kinds_of_coins) {
        return amount == 0
          ? 1
          : amount < 0 || kinds_of_coins == 0
          ? 0
          : cc(amount, kinds_of_coins - 1) +
            cc(amount - first_denomination(kinds_of_coins), kinds_of_coins);
      }

      function first_denomination(kinds_of_coins) {
        return kinds_of_coins == 1
          ? 1
          : kinds_of_coins == 2
          ? 5
          : kinds_of_coins == 3
          ? 10
          : kinds_of_coins == 4
          ? 25
          : kinds_of_coins == 5
          ? 50
          : 0;
      }