[JS]알고리즘 문제풀이6_재귀활용

coinsum 문제, 

즉 해당 잔돈들의 유형으로, 주어진 돈을 만드는 방법이 몇가지 있는지를 구하는 문제이다.

 

tip. 처음에 어떻게 풀어야 할지 감이 잡히지 않았다.
그런데 주어진 집합 내에서 중복을 허용하고, 특정 값에 다다를 때까지 합쳐준다? 는 개념에서 
가위바위보 재귀활용 알고리즘이 떠올랐다. 
우선 해당 알고리즘 문제를 활용하고 필요한 부분에 분기를 주었다.

/*

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p piece
2p piece
5p piece
10p piece
20p piece
50p piece
£1 (100p)
£2 (200p)

It is possible to make £2 in the following way:

1 * £1 + 1 * 50p + 2 * 20p + 1 * 5p + 1 * 2p + 3 * 1p
How many different ways can £2 be made using any number of coins?

example usage of `makeChange`:

// aka, there's only one way to make 1p. that's with a single 1p piece
makeChange(1) === 1
// aka, there's only two ways to make 2p. that's with two, 1p pieces or with a single 2p piece
makeChange(2) === 2
*/
 
var makeChange = function (total) {
  //total로 숫자가 주어지면 위에 언급된 잔돈들로 주어진 total을 만들 수 잇는 방법이 몇가지인가?
  //가위바위보 재귀함수를 활용할 수 있지 않을까?
  let coins = [1, 2, 5, 10, 20, 50, 100, 200].filter((coin) => total >= coin);
  // 총값보다 큰 coin은 고려하지 않아도 되므로.
  let res = [];
  let countCoin = (coinIdx, sum) => {
    if (sum === total) {
      res.push(sum);
      // 해당 sum값이 주어진 total 값과 일치하면 res 배열에 push 해주기. 그럼 해당 재귀가 종료되고 하단의 재귀종료 부분의 계산이 실행
    } else {
      //어떻게 보면 1+1+1+1+.....+1 을 해주고, 뒤에서 부터 1을 제외한 다른 값들을 넣어주며 해당하는 상황들을 찾아 주는 것.
      for (let i = coinIdx; i < coins.length; i++) {
        if (sum + coins[i] <= total) {
          // 총값이 주어진 total 값보다 작은 경우에만 재귀를 진행한다.
          sum += coins[i];
          countCoin(i, sum);
          //i=0인 상황에서 열심히 재귀가 돌아간다. 그러다가 재귀가 종료되면 아래의 수식이 실행되고,
          //코드가 한바퀴 돌았기 때문에 i=0인 경우에서 i=1로 넘어간다.
          sum -= coins[i]; // -> 재귀종료 / 그리고 i++(이때의 i는 sum 값을 total 값으로 만들어준 가장 최근의 인덱스)
        }
      }
    }
  };
  countCoin(0, 0);
  return res.length;
};