[알고리즘/인프런] 동전 교환(냅색 알고리즘)

문제

---

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

 

풀이

---

function solution(m, coin) {
  let dy = Array.from({ length: m + 1 }, () => 1000); // 가장 작은 동전으로 금액 m 만들 때보다 크게 설정
  dy[0] = 0;
  // 각 동전을 사용할 경우
  for (let i = 0; i < coin.length; i++) {
    // 해당 동전 사용 시 금액마다 필요한 동전 개수 세기
    for (let j = coin[i]; j <= m; j++) {
      dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1); // 현재 원소에서 사용하는 동전 값만큼 뺀 금액을 만들 때 필요한 동전 개수 + 1
    }
  }
  return dy[m];
}

냅색 알고리즘

- i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 가치가 더 큰 것을 가져오면 되는 것

- 이 문제에서는 각 동전을 사용했을 때와 사용하지 않았을 때를 비교해 더 적은 동전의 수를 만드는 값을 구함

 

여기서 dy[i]는 i 원을 거슬러 줄 때 필요한 최소 동전의 개수를 의미한다. dy[0]은 0원을 만드는 방법이니 0이다. 이것은 i-coin[i](현재 금액 i에서 사용하는 동전 coin[i]만큼을 뺀 금액)원을 만들기 위해 필요한 동전의 최소 개수에다 1을 더해서 구할 수 있다.

 

예를 들어, coin[i]가 5 여서 5원짜리를 사용한다고 가정해보자. 그 때 dy[5]는 어짜피 5원을 하나 사용할 것이기 때문에 dy[0], 즉 0원을 거슬러주는 방법에다 5원을 하나 사용하니 1을 더해준 값이다. 마찬가지로 dy[10] = dy[5] +1 이 된다. 여기서 1은 사용한 5원짜리 동전 1개이고, dy[5]는 그 동전을 사용하기 전의 금액을 만들기 위한 최소 동전 개수이다.