(파이썬) 백준 1676번 "팩토리얼 0의 개수"

---

# 답

N = int(input())
print(N // 5 + N // 25 + N // 125)

 

 

 

 

 

---

# 원리

 

0의 개수는 곧, 10이 몇 번 곱해져 있나를 세는 것.

10이 몇 번 곱해져 있느냐는 곧, 2와 5가 몇 번 곱해져 있냐는 것.

2와 5가 몇 번 곱해져 있느냐는 곧, 5가 몇 번 곱해져 있냐는 것.

(2의 배수가 5의 배수보다 더 촘촘히 있다. 따라서 2의 배수는 5의 배수보다 언제나 많고, 결국 5의 개수가 10의 개수를 결정한다.)

 

결국 이 문제는 N! 안에 곱해져 있는 5의 개수를 구하면 된다.

 

생각해보자.

5! 안에는 5의 배수가 몇 개 들어있는가? 1개 들어있다.(5)

6! 안에는 5의 배수가 몇 개 들어있는가? 여전히 1개 들어있다. (5)

10!안에는 5의 배수가 몇 개 들어있는가? 2개 들어있다. (5, 10)

 

여기서 규칙성이 보이는가?

N! 안에는 5의 배수가 N을 5로 나눈 몫만큼 있다.

 

그런데 주의할 점이 있다. 다음 예시를 보자.

 

아까 찾은 규칙성에 따르면

24! 안에는 5의 배수가 몇 개 들어있는가? 24를 5로 나눈 몫인 4개 들어있다. (5, 10, 15, 20)

25! 안에는 5의 배수가 몇 개 들어있는가? 25를 5로 나눈 몫인 5개 들어있다. (5, 10, 15, 20, 25)

 

여기서 질문을 조금 바꿔보겠다.

25!은 5가 몇 번 곱해져 있는가? 5번인가?

아니다. 6번이다. 왜냐하면 5, 10, 15, 20에는 5가 각각 1번씩 곱해져 있지만 25에는 5가 2번 곱해져 있기 때문이다.

정리하자면 5의 배수에는 최소 1개 이상의 5가 곱해져 있고, 25의 배수에는 최소 2개 이상의 5가 곱해져 있다고 말할 수 있다.

더 나아가서, 125의 경우도 살펴봐야한다. 125의 배수에는 최소 3개 이상의 5가 곱해져 있을 것이다.

(입력으로 주어지는 N은 최대 500이므로, 5의 거듭제곱 중에서는 5의 3승인 125까지만 살펴보면 된다.)

 

최종적으로 정리하자면,

N! 안에는 5의 배수가 N // 5 개 들어있으며, 5의 배수에는 5가 최소 1개 곱해져있다.   

→    1 * (N // 5)

N! 안에는 25의 배수가 N // 25개 들어있으며, 25의 배수에는 5가 최소 2개 곱해져있다.   

→   2 * (N // 25)

N! 안에는 125의 배수가 N // 125 개 들어있으며, 125의 배수에는 5가 최소 3개 곱해져있다. 

→   3 * (N // 125)

 

이때, 25의 배수는 5의 배수에 이미 포함되어 계산됐다. 따라서 중복을 제거해야된다.

마찬가지로 125의 배수는 5의 배수에도 포함됐고, 25의 배수에도 포함되어 계산됐다. 따라서 이 2번의 중복을 제거해야한다.

따라서 최종적인 정답은 1 * (N // 5) + 1 * (N // 25) + 1 * (N // 125)