[Algorithm] [Greedy] 편의점 알바

문제

편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.
현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

입력

인자: k
number 타입의 k
1 <= k <= 100,000,000

출력

number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.

입출력 예시

// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

풀이

function partTimeJob(k) {
  // 어떻게 풀면 좋을까
  // 최소한으로 거스름돈의 갯수를 적게 건내주기 위해서는 가장 큰수로 먼저 나누는 것이 좋은 방법이라고 생각한다.
  // 500원으로 먼저 나누고 몫이 count로 들어가게 되고, k에서 500원으로 나눈 몫을 뺀다.
  // 500원으로 나눈 몫을 뺀 k값을 이번엔 100원으로 나누고, 50원 10원 5원 1원 쭉 쭉 빼나가면 되겠다.

  // 동전이 들어있는 배열을 만들고 그 배열을 순회하면서 하나씩 나눠주면 되지 않을까?
  let count = 0
  let coin = [500, 100, 50, 10, 5, 1]

  for(let i = 0 ; i < coin.length ; i++){
    
    count += Math.floor(k / coin[i]);
    // 인덱스에 해당하는 값들로 나누어준 몫들이 coin의 갯수가 될테니, count에 추가해줌.
    // 이제 k값을 바꾸어야함.

    k = k - Math.floor(k / coin[i])*coin[i]

  }
  return count
}