[1676] 팩토리얼 0의 개수(C#)

알고리즘 : 구현
난이도 : Silver Ⅴ

 

규칙을 찾아내어야 하는 문제.

 

팩토리얼 연산을 수행하다 보면 0의 개수에 대한 규칙이 보인다.

처음에는 5의 배수만큼 0가 증가하는 것으로 판단했는데,

25쯤 가니까 갑자기 0이 추가로 증가하는 것을 보고서 단순 5의 배수가 아니라는 것을 알게됐다. (25!에서는 0가 6개..)

 

알고보니 10의 개수로 세는거였다.

그런데 이 때 10 = 2 * 5 이므로 5의 개수를 세면 된다고 착각할 수 있었는데,

음.. 비슷하다. 5의 등장 횟수보다 2의 등장 횟수가 더 많으므로.

그러나 25의 경우에는 5 * 5 이므로, 여기에 2를 두 번 곱하여 10을 만들 수 있기 때문에

10이 한번에 두번 등장하는 것과 동일하게 볼 수 있다.(일타쌍피!) 그러니까 25!을 살펴보면 아래와 같다.

 

특정 수의 약수로서 2의 등장 횟수보다 5의 동장 횟수가 적으므로 5의 개수를 세면 빠르다.

 

5의 제곱수의 경우에는 5의 등장 횟수가 중복으로 나타나니 관련 부분만 유의해서 풀어주면 된다.

이번 문제의 경우 팩토리얼 숫자 N의 범위가 500 이하이므로

5의 제곱수는 25, 125 이 두 가지 경우만 고려해 주면 된다.

 

Console.WriteLine(Math.DivRem(N,5).Quotient + Math.DivRem(N,25).Quotient + Math.DivRem(N, 125).Quotient);