우리가 그러한 금액을 가지고 있고 주어진 금액으로 합산되는 다른 교단의 최소 지폐 수를 찾아야 한다고 가정합니다. 가장 높은 금액의 지폐부터 시작하여 주어진 금액에 대해 가능한 한 많은 지폐를 찾으십시오. 여기서 {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1}의 무한한 양이 있다고 가정합니다. 따라서 금액이 800이라고 하면 메모는 500, 200, 100이 됩니다.
여기서 우리는 이 문제를 해결하기 위해 탐욕스러운 접근 방식을 사용할 것입니다.
예시
#include<iostream>
using namespace std;
void countNotes(int amount) {
int notes[10] = { 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
int noteFreq[10] = { 0 };
for (int i = 0; i < 10; i++) {
if (amount >= notes[i]) {
noteFreq[i] = amount / notes[i];
amount = amount - noteFreq[i] * notes[i];
}
}
cout << "Note count:" << endl;
for (int i = 0; i < 9; i++) {
if (noteFreq[i] != 0) {
cout << notes[i] << " : " << noteFreq[i] << endl;
}
}
}
int main() {
int amount = 1072;
cout << "Total amount is: " << amount << endl;
countNotes(amount);
} 출력
Total amount is: 1072 Note count: 500 : 2 50 : 1 20 : 1 2 : 1