★★★ 동전 교환 : Dynamic Programming (냅색 알고리즘)

내 풀이 - 가장 큰 동전으로 거슬러주고 나머지 처리

function solution(m, coin) {
  let answer = 0;
  const big_coin = coin[coin.length - 1];
  const dy = Array.from({ length: big_coin + 1 }, () => 0);

  for (let x of coin) {
    dy[x] = 1;
  }

  for (let i = dy.length - 1; i >= 1; i--) {
    let cnt = 0;
    let tmp = i;
    if (dy[i]) continue;
    for (let j = coin.length - 1; j >= 0; j--) {
      if (tmp >= coin[j]) {
        cnt += parseInt(tmp / coin[j]);
        tmp = tmp % coin[j];
      }
      if (tmp === 0) {
        dy[i] = cnt;
        break;
      }
    }
  }
  answer += parseInt(m / big_coin);
  answer += dy[m % big_coin];
  return answer;
}

let arr = [1, 2, 5];
console.log(solution(16, arr));

가장 큰 동전으로 최대한 거슬러주고, 나머지 금액을 표에 저장된 값으로 더해줌

Solution 풀이 - Dynamic Programming

function solution(m, coin) {
  let answer;
  const dy = Array.from({ length: m + 1 }, () => Number.MAX_SAFE_INTEGER);
  dy[0] = 0;
  for (let i = 0; i < coin.length; i++) {
    for (let j = coin[i]; j < dy.length; j++) {
      dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
    }
    console.log(dy);
  }
  answer = dy[m];
  return answer;
}

let arr = [1, 2, 5];

말로 설명하기가 힘들다....
그냥 여러 번 반복해 풀면서 체화시켜야 겠다 !!