[냅색 알고리즘]동전교환

문제

https://choi95.tistory.com/119?category=854389

[DFS-Cut Edge]동전교환

동전교환 문제는 이전 포스팅에서 깊이 탐색(DFS)을 통해 푼 바가 있다. 

깊이 탐색을 통해서도 해당 문제를 풀 수는 있으나 사용되는 동전 종류의 갯수가 많거나 제시된 거스름돈 금액이 많을 경우에는 시간 복잡도 상 비효율적일 수 있기 때문에 냅색 알고리즘을 통해 해당 문제를 풀이해 보고자 한다.

 

문제풀이

 

예를 들어 동전 1원만을 사용하였을 때 거슬러 줘야 될 금액이 3원인 경우 사용되는 동전의 최소 갯수는 총 3개이다.

 

이후 동전 2원을 사용하였을 경우를 생각해보자.

 

현재 참조되는 동전 2원은 반드시 최소 1개를 사용해야 동전 2원이 포함된 새로운 조합 경우수를 구할 수 있다. 

 

이에 위 이미지 상 점화식과 같이 현재 거스름돈에서 동전 2원을 우선적으로 감산했을 때의 경우는 거스러줘야 될 금액이 1원으로 

조정되고 1원을 거슬러 줄 수 있는 데 쓰인 동전 종류의 최소 갯수는 1개(동전 1원-1개)이다.

 

현재 동전 종류의 최소 갯수는 동전 2원을 가산했기 때문에 이에 대비하여 1개(동전 2원-1개)만큼을 가산하여 준다.

그렇게 되면 결과적으로 동전 3원을 거스러 줄 때 쓰인 동전 종류의 갯수는 2개(동전 1원-1개, 동전 2원-1개)이다.

 

해당 동전 종류의 갯수가 이전 dy[거스름돈]에 사용된 동전 종류의 갯수보다 작을 경우에 해당 값을 새롭게 바꿔주면 된다.

 

코드

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

  for(let i = 1; i < coin.length; i++) {
    for(let j = coin[i]; j <= change; j++) { //각 동전은 자기 자신의 금액보다 밑인 거스름돈에 대해서는 거슬러 줄 수 있는 것이 없기 때문에 초기 인덱스를 자신 자신 금액부터 시작하게끔 초기화
      let tmp = dy[j - coin[i]] + 1;
      if(dy[j] > tmp) dy[j] = tmp;
    }
  }
  answer = dy[change];
  return answer;
}

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

---

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

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