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

❓ 문제

---

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

>  입력

---

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

>  출력

---

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

✔️ 풀이

---

def f(x):
    return (x * f(x-1)) if x else 1


n = str(f(int(input())))[::-1]

for nn in n:
    if int(nn):
        print(n.index(nn))
        break

문자열로 바꿔 0이 아닌 숫자가 나올 때의 인덱스를 출력해주었다.

💬 평가

---

다른 사람들의 풀이를 봤을 때 아래와 같은 풀이가 많았다.

a = int(input())
print(a//5 + a//25 + a//125)

입력 받은수를 5의 제곱수로 나눈 몫들을 더해주는 풀이인데, 처음에 이해가 가지 않았다.

알아보니 팩토리얼 수 중에서 뒤에 0이 나오는 경우는 10이 곱해질 때라고 한다.

10은 2와 5를 곱한 수인데 왜 2의 제곱수로는 안나눠주는걸까?
2의 경우 짝수를 곱할 때마다 같이 곱해주므로 5의 제곱수의 개수보다 당연히 많을 수 밖에 없다.

따라서 이 문제의 답은 N!을 소인수분해한 후 5가 곱해진 개수 즉, 5의 지수를 구하면 된다.

5의 지수는 어떻게 구할까?

먼저 N을 5로 나눈다.

이때 문제가 생긴다.

문제에서 N의 범위는 (0 ≤ N ≤ 500)이고, 500 이하의 5의 제곱수는 5, 25(5^2), 125(5^3)가 있다.

25는 5가 2번, 125는 5가 3번 곱해진 수인데 5로만 나눈 몫을 출력하게 된다면 제대로된 지수가 나오지 않아 오답인 것이다.

따라서 25가 곱해진 경우 2씩, 125가 곱해진 경우 3씩 세주어야 한다.

따로 조건문을 사용하지 않고 쉽게 구하는 방법이 바로 위의 풀이와 같이 5, 25, 125로 나눈 몫을 더하는 것이다.

왜냐하면 25의 경우 5로 나눈 몫에서 한 번, 25로 나눈 몫에서 한 번 총 두 번씩 카운트가 되고.

125의 경우 5로 나눈 몫에서 한 번, 25로 나눈 몫에서 한 번, 125로 나눈 몫에서 한 번 총 세 번씩 카운트가 된다.

이상 풀이만 보고 이해가 되지 않아 설명해보았다.

수학 공부도 열심히 해야겠다..

Notice: 이 게시물은 백준 사이트를 참고하였습니다.