[BEAKJOON] 백준 1676번 : 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

문제

0과 500사이의 수 N을 입력받아, N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지

0의 개수를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

문제풀이

N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지 0의 개수를 출력하는 문제이다.

예를 들어, 10!은 3628800이므로, 0의 개수가 2개, 3!은 6이므로, 0의 개수가 0개가 된다.

 

문제에서 구하고자하는 바는 10(2x5)의 개수를 구하면 된다.

 

예를 들어, 10! 같은 경우에는 , 10 (2 x 5), 9, 8, 7, 6, 5, 4, 3, 2, 1 을 곱한것으로, 이의 개수가 2개가 된다.

 

그러면 문제에서 원하는 뒤에서 0의 개수를 출력하기 위해서는 숫자 2와 5를 중점적으로 보면 된다. 여기서 주목해야할 점은 "5의 개수"이다.

2의 배수는 2, 4, 6, 8, ,, 등등 5의 배수보다 매우 많기 때문에, 5의 배수의 개수를 세면, 자동으로 10의 배수가 될 것이다.

그래서 5의 제곱, 5의 세제곱의 배수 또한 마찬가지이다.

5의 제곱인 25의 배수는 5가 두개이므로, 10의 배수가 한번에 두개씩 나타나는 것과 같고,

5의 세제곱인 125의 배수는 5가 세개가 들어가 있으므로, 10의 배수가 한번에 세번씩 나타나는 것과 같다.

 

예를들어, 127이라는 수는 5의 배수가 25개, 25의 배수가 5개, 125의 개수가 1개 이므로,

127! 의 뒤에서 처음으로 0이 아닌 다른 수가 나올 때까지의 0의 개수는 25+5+1 = 31이 된다.

 

125, 25의 배수는 각각 5의 배수에 포함되어도, 5의 배수를 셀 때 한번씩만 카운트한다. 그러나 25는 5가 두개가 있고, 125는 5가 3개가 있으므로, 25는 한번, 125는 두번 더 세어주어야 한다.

125는 25에서 한번 카운트를 하기 때문에, 125때에 한번만 더 카운트만 해주면 됨으로, 모두 알맞게 더한 것이 된다.

 

문제에서 주어진 조건이 N이 0~500사이의 수이기 때문에,

5의 배수의 개수, 25의 배수의 개수, 125의 배수의 개수가 == 주어진 N!의 개수가 된다!

 

그러나 나는 25개 미만인 경우도 확인하고 싶어서 배수의 가지수가 얼마인지 확인하는 것을 저장해주었다.

 

작성 코드

num = int(input())
m_num = num
count = 0

n = 5

if (num == 0):
    print("0")
else:
    while (num // 5 != 0):
        count += 1
        num = num // 5

    result_num = 0
    for i in range(1, count + 1):
        result_num += m_num // (5 ** i)
    print(result_num)