지폐로 낼 수 있는 가짓수

#include<stdio.h> #define MAX 200 long long memo[MAX]; int pay(int money, int bills[], int n){ int count =0 , i, t; if(n==1){ if(money % bills[0] == 0) return 1; else return 0; } t = money / bills[n-1]; for(i = 0 ; i <= t ; i++){ count += pay(money-bills[n-1] * i, bills, n-1); } return count; } void main(){ int arr[]={1,2,5,10,20,50}; printf("%d\n",pay(100,arr,6)); }