[백준] 3474 - 교수가 된 현우(Python)

문제 링크

알고리즘

수학

풀이

수의 범위가 (1 <= N <= 십억) 이므로 팩토리얼을 직접 구할 수는 없다.

끝에 0이 몇 개인지 구하는 것은 인수로 10을 몇 개 포함하고 있는지 구하는 것과 같다.
예를 들어 900은 9 x 10 x 10 이므로 끝에 0이 2개이다.

하지만 팩토리얼을 직접 구할 수는 없기 때문에 소인수분해를 이용해야 한다.

10은 5와 2를 인수로 가진다. 따라서 N! 을 구하려면 몇개의 (5 x 2)가 들어있는지 구하면 된다.

정리하면 다음과 같다.

• 어떤 수의 끝에 0이 있다는 건 10 x N 과 같다.
• 10을 만들 수 있는 수는 5와 2뿐이다.

예를 들어 50! 의 끝에 0이 몇개인지 구하려고 한다.

방법은 두가지다

• 50! 에서 2의 배수의 개수를 구하거나
• 5의 배수의 개수를 구하거나

둘 중에 5가 더 크므로 5를 사용하는 것이 더 편리하다.

위에서 5의 배수를 정리하면 다음과 같다.
(5x1), (5x2), (5x3), (5x4), (5x5)
(5x6), (5x7), (5x8), (5x9), (5x10)

마지막의 (5x10) 은 (5x5x2) 와 같다.

위에서 알 수 있는 것은 다음과 같다.

50! 을 소인수분해하면 5로 12번 나눌 수 있다.
따라서 뒤에 0이 12개 붙는다.

위의 계산을 편하게 하려면 5의 배수를 구하고 5x5의 배수를 구하고 5x5x5 ... 를 구하고 그 총합을 합치면 된다. 아래는 그것을 구현한 코드이다.

코드

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())  # 수 입력 받기
    count = 0
    i = 5
    while i <= n:
        count += n // i  # 5의 배수의 합을 구한다
        i *= 5
    print(count)