문제 소개
1000, 500, 100, 50, 20, 10, 5, 2, 1 단위의 화폐 체계가 있다고 가정해 보겠습니다. 특정 금액이 주어졌을 때, 이 금액을 정확히 맞추기 위해 필요한 최소한의 화폐 개수를 계산하는 함수를 JavaScript로 작성해야 합니다.
예시
예를 들어 금액이 512라고 가정하면, 다음과 같은 조합이 최소 개수입니다.
512를 만드는 데 필요한 최소 화폐 조합:
500 단위 1장, 10 단위 1개, 2 단위 1개
따라서 금액이 512일 때 함수는 총 화폐 개수인 3을 반환해야 합니다.
접근 방식: 그리디 알고리즘
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 매 순간 가능한 한 가장 큰 단위의 화폐부터 우선적으로 차감하는 것입니다. 주어진 화폐 단위 체계에서는 큰 단위가 작은 단위들의 배수 관계를 잘 충족하므로, 이 방식이 항상 최적해를 보장합니다.
구현 코드
다음은 while 루프와 조건문을 활용해 작성한 전체 코드입니다.
const sum = 512;
const countNotes = sum => {
let count = 0;
while(sum){
if(sum >= 1000){
sum -= 1000;
count++;
continue;
}else if(sum >= 500){
sum -= 500;
count++;
continue;
}else if(sum >= 100){
sum -= 100;
count++;
continue;
}else if(sum >= 50){
sum -= 50;
count++;
continue;
}else if(sum >= 20){
sum -= 20;
count++;
continue;
}else if(sum >= 10){
sum -= 10;
count++;
continue;
}else if(sum >= 5){
sum -= 5;
count++;
continue;
}else if(sum >= 2){
sum -= 2;
count++;
continue;
}else{
sum -= 1;
count++;
continue;
}
};
return count;
};
console.log(countNotes(sum));
코드 동작 원리
while 루프는 남은 금액이 0이 될 때까지 반복됩니다. 각 반복마다 현재 남은 금액보다 작거나 같은 가장 큰 화폐 단위를 찾아 금액에서 차감하고, 사용한 화폐 개수(count)를 하나씩 증가시킵니다. 예를 들어 512가 입력되면 500 → 12 → 10 → 2 → 0 순서로 차감되며, 총 3번의 차감 과정을 거칩니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
3
결과적으로 금액 512를 만들기 위해 필요한 최소 화폐 개수인 3이 올바르게 반환되는 것을 확인할 수 있습니다.