2004번 조합 0의 개수 - ☆

#문제링크 : 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