- 17 名前：デフォルトの名無しさん mailto:sage [2010/06/18(金) 11:25:37 ]
- >>5
#include <stdio.h>
int min;
void count(int n, int idx, int cnt, int *coin)
{
int i, temp = coin[idx];
if(n % temp == 0) {
cnt += n / temp;
if(cnt < min) min = cnt;
return;
}
for(i = 0; i * temp < n; i++) count(n - i * temp, idx-1, cnt + i, coin);
}
int main(void)
{
int coin[] = {1, 5, 8, 10, 15}, n;
scanf("%d", &n);
min = n;
count(n, sizeof coin / sizeof *coin - 1, 0, coin);
printf("%d\n", min);
return 0;
}
