[ 자바스크립트(JavaScript) ] section10 - 4 - 동전 교환(냅색 알고리즘)

📍 section10 - 4 - 동전 교환(냅색 알고리즘)

문제: 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

 

// 입력
3
1 2 5
15

// 출력
// (5, 5, 5) 동전 3개로 거슬러 줄 수 있다.
3

 

동전교환 문제는 저번에 dfs(부분집합) + edgeCut을 이용해서 푼 적이 있다. 만약에 동전의 종류가 100개 이상, 거스름 돈이 100,000 이상일 경우 DFS로 풀 수 없다. 이럴 때는 DP에서 냅색 알고리즘으로 풀어야 한다.

 

1. dp는 거슬러줄 돈(m)만큼 배열의 크기를 선언하고 최소 동전의 개수를 구해야 하므로 개수를 제일 많이 거슬러주는 개수보다 큰 값으로 설정한다.(문제에서 금액은 최대 500원까지인데, 다른 동전에 비해 1원으로 500원을 거슬러주는 개수가 제일 많으므로 1원짜리 동전 500개가 필요하므로 dp는 500보다 큰 값으로 초기화 시킨다. )
2. dp[j]: j 금액을 거슬러 줄 때 사용되는 최소 동전의 개수
3. 핵심 로직: 현재 거슬러줘야 할 동전의 금액만큼 빼주고 이전에 거슬러 줬던 동전의 최소 개수 + 1 (현재 내가 거슬러주는 동전의 개수)
4. 0원을 거슬러주는 동전의 개수 dp[0]=0
5. n원은 dp[n]부터 시작한다.

 

 

728x90

 

let n = 3;
let coin = [1, 2, 5];
let change = 15;

console.log(solution(n, coin, change));

function solution(n, coin, change){
  let dp = Array.from({length: change+1}, () => 1000);
  dp[0]=0;  // 0원을 거슬러 주는 경우의 수 0

  for (let i=0; i<n; i++){
    for (let j=coin[i]; j<=change; j++){
      dp[j]=Math.min(dp[j], dp[j-coin[i]]+1);
    }
  }
  return dp[change];
}

👉🏽 3