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

 

 

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

문제 바로 가기

---

📌 문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

 

 

📝 문제 접근 방법

아이디어

1. 팩토리얼의 정의

• 팩토리얼 $N!$은 $1 \times 2 \times 3 \times \cdots N$으로 정의됩니다.
• 예를 들어
  • $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$
  • $10! = 1 \times 2 \times 3 \times \cdots \times 10 = 3,628,000$
• 팩토리얼 값의 뒤쪽에 나타나는 0은 곱셈 과정에서 만들어진 10 때문이므로 10이 만들어지는 과정을 이해하면 뒤쪽 0의 개수를 계산할 수 있습니다.

 

2. 10이 만들어지는 원리

• 숫자 10은 $10 = 2 \times 5$로 표현됩니다.
• 즉, 곱셈 과정에서 2와 5가 짝을 이루면 10이 만들어지고 뒤에 0이 추가됩니다.
• 예를 들어
  • $2 \times 5 = 10$: 뒤에 0이 1개 추가
  • $4 \times 25 = 100$: 뒤에 0이 2개 추가 

 

3. 팩토리얼에서 2와 5의 개수 비교

• 팩토리얼에서는 $1 \times 2 \times 3 \times \cdots N$으로 이루어져 있습니다.
  • 이 중 2, 4, 6, 8, 10, ... 와 같은 짝수는 항상 충분히 많습니다.
  • 하지만 5, 10, 15, 20, ... 와 같은 5의 배수는 상대적으로 적습니다.
• 2와 5가 한 쌍을 이루어야 10이 만들어지는데 2는 항상 충분히 많으므로 5의 개수만 계산하면 됩니다.

 

4. 팩토리얼에서 5의 개수 구하기

• 팩토리얼에서 5, 10, 15, 20, ... 와 같은 5의 배수는 최소한 하나의 5를 포함합니다.
  • 25, 50, 75, ... 와 같은 5의 제곱수는 2개 이상의 5를 포함합니다.
  • 125, 250, ... 와 같은 5의 세제곱 이상의 수는 세 개 이상의 5를 포함합니다.
• 따라서 팩토리얼의 뒤쪽 0의 개수는 다음 공식으로 계산할 수 있습니다.

$$\text{Trailing zeros} = \left\lfloor \frac{N}{5} \right\rfloor + \left\lfloor \frac{N}{25} \right\rfloor + \left\lfloor \frac{N}{125} \right\rfloor + \dots$$

 

 

 

👩‍💻 나의 답안

def trailing_zeros_in_factorial(n):
    count = 0
    power_of_5 = 5
    while n >= power_of_5:
        count += n // power_of_5
        power_of_5 *= 5
    return count

n = int(input())

print(trailing_zeros_in_factorial(n))

 

 

 

✨ 새로 알게 된 점

1. 팩토리얼에서 뒤쪽 0의 개수

팩토리얼 값에서 뒤쪽 0의 개수는 곱셈 과정에서 만들어지는 $10 = 2 \times 5$의 개수로 결정된다는 점을 알게 되었습니다. 팩토리얼에서는 짝수(2)가 항상 충분히 많아 10이 만들어지려면 5만 추가적으로 필요합니다. 따라서, 뒤쪽 0의 개수는 팩토리얼에 포함된 5의 개수만 계산하면 되는 문제로 단순화할 수 있다는 점이 흥미로웠습니다.