Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
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
Tags
more
Archives
Today
Total
관리 메뉴

빠똥빠똥

2004번 조합 0의 개수 - ☆ 본문

백준

2004번 조합 0의 개수 - ☆

조주똥 2020. 7. 12. 18:04

#문제링크 : https://www.acmicpc.net/problem/2004

<전략>

1. n!의 0의 갯수는 1~n까지 5가 몇번나오느냐와 같다. 0은 2 x 5 = 10 으로부터 나오기 때문인데, 2는 5에 비해 훨씬 많이 나오게 된다. 따라서 소인수분해 했을때, 5가 몇번 나오는지만 세어주면 뒤에 붙는 0에 갯수를 알 수 있다.

2. 반면, 조합은 2와 5중 어떤것이 더 많이 도출되는지 알 수 없다. 따라서 2와 5중에서 더 적게 나오는 수의 갯수가 0의 갯수가 된다.

Code