[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

📌 해당 문제에서는 제시된 금액에서 가장 큰 금액부터 빼면서 그 수를 세어가야 하고, 마지막에 금액이 동전의 수와 같아졌을 때 조건문을 종료한다.

1. 제시된 k가 0이 될 때까지 조건문을 돌린다.
2. 동전으로 계산이 가능한 경우 k에서 동전 금액을 빼고 숫자를 카운트 해준다.
3. 만약 남은 금액이 동전 금액보다 낮을 경우 동전 금액을 1개씩 낮춰준다.
4. 동전으로 계산은 가능하지만 k에서 해당 동전 금액을 뺐을 때 0이 되는 경우 조건문을 종료한다.
   5.카운트 한 갯수를 리턴해준다.

function partTimeJob(k) {
    let answer = 0;
    let coin = [1, 5, 10, 50, 100, 500];

    while ( k > 0 ) {
        if ( k > coin[coin.length-1]) {
            k = k - coin[coin.length-1]
            answer++
        }
        else {
            if ( k === coin[coin.length - 1] ) {
                answer++
                break;
            }
            coin.pop()
        }
        
    }
    return answer;
}