[python] 백준 1676번

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

문제

---

소스코드

1. 팩토리얼 구현 O

n = int(input())

i = 2
result = 0
factorial = 1

while 1:
    if i == (n + 1) or n < 4:
        break

    factorial *= i
    i += 1

for i, s in enumerate(str(factorial)[::-1]):
    if s != "0":
        result = i
        break

print(result)

2. 팩토리얼 구현 X

n = int(input())

result = 0
square_5 = 5

while square_5 <= n:
    result += n // square_5
    square_5 *= 5

print(result)

---

풀이

1. 팩토리얼을 계산하고 결과값에서 반복문을 이용하여 0의 개수를 구하는 방법이다.

2. 0의 개수를 구한다는 것은 10의 개수를 구하는 것과 같다. 따라서 10을 소인수분해한 2x5의 개수를 구하는데 2는 배수가 너무 많기 때문에 5의 배수의 개수를 세면 그것이 10의 배수의 개수가 된다.

   5의 제곱수는 5가 중복해서 들어가기 때문에 개수도 중복해서 계산해야 한다.
   중복해서 계산하는 것이 어렵다고 느낄수도 있지만 5의 배수에 제곱수 25, 125가 포함되고 25의 배수에 125가 포함되기 때문에 별도의 계산은 하지 않고 5의 배수의 개수, 25의 배수의 개수, 125의 배수의 개수, . . .를 더하면 팩토리얼의 0의 개수를 구할 수 있다.

---

참고한 사이트