문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

입력
인자 1: target
Number 타입의 100,000 이하의 자연수
인자 2: type
Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열
출력
Number 타입을 리턴해야 합니다.
조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.
주의사항
모든 화폐는 무한하게 있다고 가정합니다.

입출력 예시
let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4
Hint!
해당 문제는 동전 교환 알고리즘 (Coin Change)을 활용하여 풀 수 있습니다.
검색해 보시고, 연구해 보세요!

내 풀이

function ocean(target, type) {
  // TODO: 여기에 코드를 작성합니다.
  // ocean(target) = for(let t of type){result += ocean(target - t)}
  // ocean(t) = if(target === 0){return 0}
  // if(type.includes(target)){result++;}

  if(target === 0){ 
    return 0;
  }
  return coin(target, type);


  function coin(target, type){ 
    let result=0;

    if(target === 0){ 
      return 1; 
    }

    for(let i=0; i<type.length;i++){ 
      if(target-type[i]>=0){
      result += coin(target-type[i], type);
      }
    }

    return result;

  }

}

ERROR #1. callstack exceeded
ERROR #2. 같은 방법을 다르게 세서 경우의 수가 더 많이 나옴
ex. 10 10 10 20 , 10 10 20 10을 다르게 센다
간과한 point : 재귀로 들어가면서 가장 base case부터 for문을 하나씩 빠져나오기 때문에 각 i마다 3의 n지수를 돌게 됨

레퍼런스

function ocean(target, type) {
  // bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
  // 각 인덱스 no# = 만드려는 금액 을 의미
  // ex) target = 5, type = [1, 2, 5] 면
  // bag[3] = 2  => 3을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용
  // bag[4] = 3  => 4를 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 & 2만 사용 
  // bag[5] = 4  => 5를 만드는 경우의 수 = 1*5 , 1*3 + 2, 1 + 2*2, 5*1
  // 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
  -> 이것보다는 2를 만들 때 2를 사용해서 만드는 경우의 수는 1이기 때문에 
  bag[2-2] = 1이어야 하므로 1이라고 생각하는 게 더 편하다 
  
  let bag = [1];

  // 인덱스 no# = 만드려는 금액 이기 때문에
  // bag 을 target 금액만큼의 길이를 가진 배열을 만들어 주고,
  // 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
  for(let i = 1; i <= target; i++)
    bag[i] = 0;
  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색   
  for(let i = 0; i < type.length; i++) {
  // target 금액까지 순차적으로 1씩 증가하면서    
   **for(let j = 1; j <= target; j++)**
  // bag의 인덱스가 type[i] 보다 큰 구간만
  // (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)    
  **if(type[i] <= j)**
  // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다       
        bag[j] += bag[j-type[i]];
  }
  // bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
  // 해당 값을 리턴해 준다
  return bag[target];
}

여기서 내가 저지른 오류를 피할 수 있었던 이유는 type의 요소를 기준으로 0~target 각각의 경우의 수를 합했기 때문이다

for(let i = 0; i < type.length; i++) {

  **for(let j = 1; j <= target; j++)**

 **if(type[i] <= j)**
     
       bag[j] += bag[j-type[i]];
 }

이게 무슨 말이냐면 예를 들어 type=[2,3,5], target=5일 때,
i for문을 통해 type의 요소를 먼저 돈다
그러므로 type=2일 때 2만으로 1~5까지 만들 수 있는 경우의 수를 bag에 저장하고
type=3일 때는 2만으로 만들 수 있는 경우의 수를 바탕으로 3으로 만들 수 있는 경우의 수를 bag에 저장하고
type=5일 때는 이전에 저장된 값들을 바탕으로 5만으로 만ㄷ르 수 있는 경우의 수를 bag에 저장한다

즉 내 오류는 target을 위주로 type의 요소들을 하나씩 빼면서 구했기 때문에 순서가 다르면 다른 경우로 인식을 했지만
레퍼런스처럼 type을 위주로 type의 요소들을 각각 독립적으로 활용하면 중복 없이 경우의 수를 합할 수 있다

이렇게 독립적으로 구해서 더할 수 있는 이유는 type의 각 요소들을 더하는 것은 경우의 수가 한가지로 이전의 값에 곱하기 1을 하는 거나 다름 없기 때문이다. 예를 들어 5를 만들 때 3을 포함한 경우의 수는 5-3=2이기에 type의 요소로 2를 만드는 방법의 수와 같기 때문이다. +3을 하는 것은 여러 경우의 수가 있는 것이 아니라 오직 한가지 경우이기 때문에 *1을 하는거나 다름이 없기 때문이다.