동전 교환(coin change) 알고리즘 문제

백준 2293번 동전1
코플릿 문제 : 금고를 털어라

문제

target 금액과, n개의 종류의 돈이 있을 때
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

풀이

i번째 코인까지 사용해 target을 만드는 모든 경우의 수는 i-1 번째 코인까지 사용해 sum을 만드는 경우의 수와 i 번째 코인까지 사용해 (sum에서 i번째 코인의 액면가를 뺀 금액)을 만드는 경우의 수를 합한 것과 같다.

첫 번째 입출력 예시로 생각해보자,
target 값이 50원일 때,

1. 10원으로 만들 수 있는 경우의 수는 1개(10원 x 5개)이다.

2. 10원, 20원으로 만들 수 있는 경우의 수는 3개이다.

• 10원만으로 50원을 만들 수 있는 경우의 수 + 10원과 20원으로 (50원 - 20원)을 만들 수 있는 경우의 수

3. 10원, 20원, 50원으로 만들 수 있는 경우의 수는 4개이다.

• 10원, 20원으로 50원을 만들 수 있는 경우의 수 + 10원 20원,50원으로 (50원 - 50원)을 만들 수 있는 경우의 수(1개)

0원을 만드는 경우의 수는 1개(동전을 0개 사용)이다.
단, 동전이 0개 있는 경우 경우의 수는 0개이다.

풀이1 반복문

function ocean(target, type) {
  let bag = Array(target+1).fill(0);
  bag[0] = 1;

  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]];
      }
    }
  }
  return bag[target];
}

풀이2 재귀

function ocean(target, type) {
  const memo = Array.from(Array(type.length), () =>
    Array(target + 1).fill(false)
  );
  const change = (i, sum) => {
    if (sum < 0 || i < 0) return 0;
    if (sum === 0) return 1;

    if (memo[i][sum]) return memo[i][sum];
    return (memo[i][sum] = change(i - 1, sum) + change(i, sum - type[i]));
  };

  return change(type.length - 1, target);
}

참고 : https://dong-jinmyong.tistory.com/24