暑期训练2：AtCoder Beginner Contest 208 B - Factorial Yen Coin

B - Factorial Yen Coin
Time Limit: 2 sec Memory Limit: 1024 MB

Score :
200
points

Problem Statement
The coins used in the Kingdom of Takahashi are
1
!
-yen coins,
2
!
-yen coins,
…
, and
10
!
-yen coins. Here,
N
!

1
×
2
×
⋯
×
N
.

Takahashi has
100
of every kind of coin, and he is going to buy a product worth
P
yen by giving the exact amount without receiving change.

We can prove that there is always such a way to make payment.

At least how many coins does he need to use in his payment?

Constraints
1
≤
P
≤
10
7
P
is an integer.
Input
Input is given from Standard Input in the following format:

P

Output
Print the minimum number of coins needed.

Sample Input 1
Copy
9
Sample Output 1
Copy
3
By giving one
(
1
!

)
1
-yen coin, one
(
2
!

)
2
-yen coin, and one
(
3
!

)
6
-yen coin, we can make the exact payment for the product worth
9
yen. There is no way to pay this amount using fewer coins.

Sample Input 2
Copy
119
Sample Output 2
Copy
10
We should use one
1
!
-yen coin, two
2
!
-yen coins, three
3
!
-yen coins, and four
4
!
-yen coins.

Sample Input 3
Copy
10000000
Sample Output 3
Copy
24
题解：本题就是相当于简单的背包问题，我们用一个数组对于各种阶乘的值进行相关的保存，此时就是利用简单的贪心思想进行相关的组合数的值的挑选即可，利用ans进行相关的数目统计即可完成本题的解答。

#include<bits/stdc++.h>
using namespace std;
long long f[22]={1,1}; 
int main()
{
	for(long long i=2;i<=10;i++)
	  f[i]=f[i-1]*i;
	long long n;
	cin>>n;
	int now=10;
	int ans=0;
	for(;;)
	{
		while(f[now]>n) --now;
		ans+=n/f[now];
		n%=f[now];
		--now;
		if(n==0)
		  break;
	}
	cout<<ans<<endl;
	return 0;
}