1234567891011121314151617181920212223242526 |
- #include <bits/stdc++.h>
- using namespace std;
- int values[5] = {1, 2, 4, 5, 10};
- int coin[100001];
- void init() {
- coin[0] = 0;
- int Min = 0;
- for (int i = 1; i <= 100001; i++) {
- Min = i;
- for (int j = 0; j < 5; j++) {
- if (values[j] <= i) {
- Min = min(Min, coin[i - values[j]] + 1);
- }
- }
- coin[i] = Min;
- }
- }
- int main() {
- init();
- int money;
- while (cin >> money) {
- cout << coin[money] << endl;
- }
- return 0;
- }
|