JavaScript Algorithm - coinChange

문제

다양한 동전들을 가지고 특정 금액을 만들 수 있는 모든 경우의 수를 리턴해야 합니다.

• 예를 들어, 100원, 500원짜리 동전을 가지고 1,000원을 만들 수 있는 방법은 총 3가지 입니다.
• 100원 10개, 100원 5개 + 500원 1개, 500원 2개 
• 위의 경우를 다 합치면 총 3개의 방법이 나옵니다. 더 자세한 것은 입출력 예시를 통해 보시고 그래도 이해가 안된다면 console.log 출력 부분을 보시고 감을 잡으시면 됩니다. 

입력

인자 1 : total

• number 타입의 이하의 자연수

인자 2 : coins

• number 타입을 요소로 갖는 배열
• coins.length는 10,000 이하
• coins[i]는 20 이하의 양의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 동전의 금액은 다양하게 주어집니다.
• coins는 오름차순으로 정렬되어 있습니다.
• 각 동전의 개수는 무수히 많다고 가정합니다.

입출력 예시

let total = 10;
let coins = [1, 5];
let output = coinChange(total, coins);
console.log(output); // --> 3

total = 4;
coins = [1, 2, 3];
output = coinChange(total, coins);
console.log(output); // --> 4 ([1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3])

 

풀이 코드:

function coinChange(total, coins) {
  // 초기값이 0인 총 +1 크기의 배열 dp를 만든다. 이 배열은 주어진 코인을 사용하여 각 금액을 만들 수 있는 방법의 수를 저장합니다.
  const dp = new Array(total + 1).fill(0); 
  console.log("dp 1",dp)
  dp[0] = 1; //  0을 버는 한 가지 방법이 있기 때문에 dp 배열의 첫 번째 요소를 1로 초기화합니다
  console.log("dp 0 초기화",dp)
  //동전 배열의 각 동전을 반복한다.
  for (const coin of coins) {
    console.log("coin",coin)
    //각 코인에 대해 코인 값에서 총계까지 dp 배열을 반복합니다.
    for (let i = coin; i <= total; i++) {
      console.log("dp before",dp)
      dp[i] += dp[i - coin]; //코인부터 총계까지 각각의 i에 대해 현재 코인을 사용하여 현재 금액 i를 만드는 방법의 수를 누적합니다. 이것은 dp[i]에 dp[i-coin]의 가치를 더함으로써 이루어진다.
      console.log("dp after",dp)
    }
    console.log("dp 2",dp)
  }
  console.log("dp 3",dp)
  return dp[total]; // 모든 코인과 모든 금액을 반복하면 dp[총] 값에 주어진 코인을 사용하여 주어진 총 금액을 만들 수 있는 총 방법 수가 포함됩니다.
}
let total = 10;
let coins = [1, 5];
let output = coinChange(total, coins);
console.log(output); // --> 3

// total = 4;
// coins = [1, 2, 3];
// output = coinChange(total, coins);
// console.log(output); // --> 4 ([1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3])

 

 

 

 

console.log 예시

로직 이해를 위해 확인한 console.log 데이터 

dp 1 [
  0, 0, 0, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp 0 초기화 [
  1, 0, 0, 0, 0,
  0, 0, 0, 0, 0,
  0
]
coin 1
dp before [
  1, 0, 0, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 0, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp before [
  1, 1, 0, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp before [
  1, 1, 1, 0, 0,
  0, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 0,
  0, 0, 0, 0, 0,
  0
]
dp before [
  1, 1, 1, 1, 0,
  0, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  0, 0, 0, 0, 0,
  0
]
dp before [
  1, 1, 1, 1, 1,
  0, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 0, 0, 0, 0,
  0
]
dp before [
  1, 1, 1, 1, 1,
  1, 0, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 1, 0, 0, 0,
  0
]
dp before [
  1, 1, 1, 1, 1,
  1, 1, 0, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 1, 1, 0, 0,
  0
]
dp before [
  1, 1, 1, 1, 1,
  1, 1, 1, 0, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 0,
  0
]
dp before [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 0,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 1,
  0
]
dp before [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 1,
  0
]
dp after [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 1,
  1
]
dp 2 [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 1,
  1
]
coin 5
dp before [
  1, 1, 1, 1, 1,
  1, 1, 1, 1, 1,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 1, 1, 1, 1,
  1
]
dp before [
  1, 1, 1, 1, 1,
  2, 1, 1, 1, 1,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 2, 1, 1, 1,
  1
]
dp before [
  1, 1, 1, 1, 1,
  2, 2, 1, 1, 1,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 2, 2, 1, 1,
  1
]
dp before [
  1, 1, 1, 1, 1,
  2, 2, 2, 1, 1,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 1,
  1
]
dp before [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 1,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 2,
  1
]
dp before [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 2,
  1
]
dp after [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 2,
  3
]
dp 2 [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 2,
  3
]
dp 3 [
  1, 1, 1, 1, 1,
  2, 2, 2, 2, 2,
  3
]
3