문제

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

입출력 예제

입력 : [1, 2, 5]
출력 : 3

코드

function solution(arr, money) {
    let answer = 0;
    //	동전 값이 큰 순서대로 정렬
  	arr.sort((a, b) => b - a)
    for(let i = 0; i < arr.length; i++ ) {
      	// 거슬러줘야 하는 금액을 동전 갯수로 나눈 값 더하기
        answer += (money / arr[i])
      	// 나머지로 남은 거스름돈 업데이트
        money %= arr[i]
    }
    return answer
}

console.log(solution([1, 2, 5], 150))	// 3