[ 자바스크립트(JavaScript) ] section08 - 9 - 동전교환

📍 section08 - 9 - 동전교환

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

// 입력
3
1 2 5
15

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

 

거스름돈 문제는 그리디로 풀어본 적 있다. 하지만, 이 문제는 그리디로는 풀 수 없다. 왜냐하면 동전의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우기 때문이다. 이럴 땐 DFS 혹은 DP를 이용하면 된다. 만약, 동전이 [500, 100, 50, 10]처럼 배수형태로 나오면 그리디로 풀 수 있다.

 

또, 앞서 배운 부분집합으로는 이 문제를 풀 수 없는데, 왜냐하면 동전을 각 한 번씩 쓰는 것이 아니고 거스름돈이 더 이상 없어질 때까지 무한정으로 쓸 수 있기 때문이다. 이럴땐 모든 경우의 수를 구하는 방법 혹은 `DP`로 계산하는 방법이 남았는데,  동전의 개수가 커질수록 계산하는 가짓수도 늘어나기 때문에 edgeCut을 이용했다. 11, 12번 라인처럼 조건을 걸어주면 연산 횟수를 대폭 낮출 수 있다. 약간의 팁을 추가하자면 coin을 내림차순으로 정렬을 하고나서 DFS로 들어가는 것인데, 정렬하는데 시간이 조금 들더라도(O(NlogN)) 거스름돈은 동전의 큰 단위를 먼저 주는 것이 횟수를 낮출 수 있기 때문이다. 거스름돈을 큰 단위부터 바꿔줄 때 재귀 흐름도는 다음과 같다.

 

728x90

 

 

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

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

function solution(n, coin, change) {
    let answer = Number.MAX_SAFE_INTEGER;
    coin.sort((a, b) => b - a);  // 거스름돈을 큰 단위부터 바꿔주면서 연산횟수를 단축시킨다.

    function DFS(L, sum) {
        if (sum > change) return;    // change보다 sum이 크면 더 이상 계산 할 필요가 없음.
        if (answer <= L) return;    // answer보다 작은 값을 구해야하는데 L이 더 크면 가지치기를 더 이상 할 필요가 없음.
        if (sum === change) {
            answer = Math.min(answer, L);
        } else {
            for (let i = 0; i < n; i++) {
                DFS(L + 1, sum + coin[i]);
            }
        }
    }

    DFS(0, 0);
    return answer;
}