잔돈 바꾸기를 더 효율적으로 짜는 방법이 뭐가 있을까요?

Money System 문제 같은데...

아마 Greedy로는 Optimal Solution이 나오지 않을겁니다.

저는 Dynamic 으로 풀었었습니다.

ACMICPC에 나오는 문제거든요.

비슷한 문제가 어떤 아이가 N번째 계단을 오르는데 한번에 1계단, 2계단만

오를수 있다면, N번째 계단까지 오를수 있는 경우의 수를 구하는 문제입니다.

하지만 다른점은 계단문제에서는 순서가 있습니다.

1계단 -> 2계단 과
2계단 -> 1계단 이런식으로 순서가 존재하죠

하지만 Money System에서는

1원 + 2원
2원 + 1원은 같은 것이 되겠죠.

#include<stdio.h>

int coins[10] = { 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000};
int nways[5001];
float money;

main(){

        int i, j;

        nways[0] = 1;

        for(i = 0; i < 10; i++){
                for(j = coins[i]; j < 5001; j++) 
                         nways[j] += nways[j - coins[i]];
        }

        while(scanf("%f", &money) > 0 && money != 0){
                float tmp = money * 100;
                printf("%5.2f%12d\n", money, nways[(int)tmp]);
        }
        return 0;
}

이건 그때 풀었던 소스입니다.