백준 22.03.23. 1676번 - 팩토리얼 0의 개수

n = int(input())

cnt = 0

while n >= 5:
    
    cnt += n//5
    
    n//=5

print(cnt)

• n! = 1*2*3*4....*n입니다.
• n!의 결과값이 뒤에서부터 0을 가지기 위해서는 10의 배수가 곱해져야합니다.
  • 이유는 n!를 소인수분해를 했을 때 2ⁿ*5ⁿ만큼 뒤에서부터 0을 가지기 때문입니다.
  • 10 = 2*5입니다.
• 구조상 n!는 5의 배수가 2의배수보다 적습니다.
• 따라서 5의 배수의 개수를 구하여 출력해주면 됩니다.
  • n!에서 5의 배수의 개수를 구하려면 n / 5 를 하면 알 수 있습니다.
    • =>만약 n이 100이라면 5, 10, 15... 100처럼 5의 배수들은 모두 n*5의 형태를 가지므로 5를 하나씩 포함한다고 볼 수 있습니다.
    • 여기서 하지만 25의 배수들은 25 = 5*5이므로 5를 두번 포함합니다.
    • 따라서 100 / 5 = 20 이므로 cnt += 20을 해주고 20 / 5 를 하여 25,50,75,100과 같이 5를 두번 포함하는 수들의 개수를 구해줄 수 있습니다.
      • n/5를 한 번 할때마다 1차라고 한다면 1차식은 5의 1제곱의 개수를 구하고 2차는 5의 2제곱, n차는 5의 n제곱의 개수를 구해나가는 식입니다. 이 모두를 cnt에 모아주면 n!이 5의 cnt제곱을 약수로 가진다는 것을 알 수 있습니다.
    • 따라서 100!를 소인수분해 했을 때 5는 cnt제곱만큼 계산되므로 
  • 25와 같이 5의 n제곱형태를 가지는 수를 계산하기 위해서 n//5를 반복하며 cnt를 추가해줍니다.
• cnt 가 n!를 소인수분해 했을때 5의 k 제곱을 나타내는 k 가 됩니다.
• 이것을 출력하면 됩니다.