-
Notifications
You must be signed in to change notification settings - Fork 0
/
change.c
57 lines (53 loc) · 1.28 KB
/
change.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int indent = 0;
int
change(int price, int * currencies, int currencies_len) {
static int min_change[50100];
min_change[0] = 0;
int i = 1;
for (; i <= price; i++) {
int min = INT_MAX;
int currency_i = 0;
for (; currency_i < currencies_len; currency_i++) {
int remain = i - currencies[currency_i];
if (remain < 0) continue;
int the_change = min_change[remain] + 1;
min = the_change < min ? the_change : min;
}
if (min == INT_MAX) {
min_change[i] = 0;
} else {
min_change[i] = min;
}
//printf("%d ", min_change[i]);
}
//puts("");
return min_change[price];
}
int *
create_currencies(int len) {
static int currencies[110];
memset(currencies, 0, sizeof(currencies));
return currencies;
//return calloc(len, sizeof(int));
}
int
main(void) {
int currencies_len, price;
while (1) {
scanf("%d%d", ¤cies_len, &price);
if (currencies_len == 0 &&
price == 0) break;
int * currencies = create_currencies(currencies_len);;
int i = 0;
for (; i < currencies_len; i++) {
scanf("%d", ¤cies[i]);
}
printf("%d\n", change(price, currencies, currencies_len));
//free(currencies);
}
return 0;
}