백준 - 1676번 팩토리얼 0의 개수 python 문제풀이 [Hellfer]

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

1676번: 팩토리얼 0의 개수

🔷 알고리즘 분류 - 수학, 난이도 - 실버 5

🔶문제 풀이 - 5의 개수를 세는 풀이

팩토리얼에서 0이 나오는 경우는 10의 배수가 되는 경우입니다. 

 

10은 2와 5의 곱으로 이루어져 있으며, 팩토리얼에서 2의 개수는 항상 5의 개수보다 많습니다. 

 

따라서 5의 개수를 세는 것으로도 팩토리얼의 끝에 연속해서 나오는 0의 개수를 구할 수 있습니다.

이 코드에서는 주어진 숫자 n을 5로 나눈 몫을 구하고, 그 몫을 다시 5로 나눈 몫을 구하는 과정을 반복하여 5의 개수를 누적합니다. 

 

이를 통해 팩토리얼의 끝에 연속해서 나오는 0의 개수를 계산할 수 있습니다.

즉, 이 코드는 주어진 숫자 n의 팩토리얼에서 5의 개수를 세어서 0의 개수를 구하는 알고리즘을 사용합니다.

 

import sys

def count_zero(n):
    count = 0
    while n > 0:
        n //= 5
        count += n
    return count

n = int(sys.stdin.readline().rstrip())  # 입력값을 표준 입력을 통해 받아옴

result = count_zero(n)  # 팩토리얼의 끝에 연속해서 나오는 0의 개수 계산

print(result)  # 결과 출력

 

🔶 초보자를 위한 생각주머니 키우기

🔸5의 개수를 세는 이유?

이 코드에서 5의 개수를 세는 이유는 10의 배수가 되는 경우에만 0이 나오기 때문입니다.

팩토리얼에서 0이 나오는 경우는 10의 배수가 되는 경우입니다. 

 

10은 2와 5의 곱으로 이루어져 있습니다. 

 

따라서 팩토리얼에서 0의 개수를 구하려면 2와 5의 개수를 세어야 합니다.

여기서 주목할 점은 팩토리얼에서 2의 개수는 항상 5의 개수보다 많다는 것입니다. 

 

왜냐하면 2는 짝수인 숫자들에 항상 포함되어 있기 때문입니다. 

 

그래서 팩토리얼에서 5의 개수를 세는 것으로도 0의 개수를 구할 수 있습니다.

이 코드에서는 입력된 숫자 n을 5로 나눈 몫을 구하고, 그 몫을 다시 5로 나눈 몫을 구하는 과정을 반복하여 5의 개수를 누적합니다. 

 

이를 통해 팩토리얼의 끝에 연속해서 나오는 0의 개수를 계산할 수 있습니다.

따라서 이 알고리즘은 주어진 숫자의 팩토리얼에서 0의 개수를 효율적으로 구하기 위해 5의 개수를 세는 방법을 사용합니다.

🔸다른 예시

입력값이 25인 경우:

n을 5로 나눈 몫은 5입니다. (n //= 5)

count에 5를 더합니다. (count += n)

결과적으로 count는 5입니다. 

 

따라서 25의 팩토리얼의 끝에는 5개의 연속된 0이 있습니다.

입력값이 30인 경우:

n을 5로 나눈 몫은 6입니다. (n //= 5)

count에 6을 더합니다. (count += n)

결과적으로 count는 6입니다. 

 

따라서 30의 팩토리얼의 끝에는 6개의 연속된 0이 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗