[백준]_1676 : 팩토리얼 0의 개수(파이썬 and C언어)

1676번: 팩토리얼 0의 개수

그냥 n! 을 10으로 계속 나눠서 그 나머지가 0이 아닐 때까지 반복하면 되는 거 아닌가 싶었던 문제이다. 하지만 n이 500까지 허용된다는 것을 간과한 결과 나는 장렬히 런타임에러로 전사하였다. 왜냐하면 500! 은 대략 10의 1134승이기 때문이다... 따라서 직접 n! 을 구하고 나누는 것이 아닌 다른 전략이 필요하다

---

전략

0의 개수는 무엇에 의해 결정될까? 물론 문제에서 요구하는 것은 1의 자리부터 시작된 연속된 0의 개수이다. 따라서 1023400과 같은 숫자일 경우 2만 출력하면 되는 것이다.

뒷자리 0의 개수는 2와 5의 쌍이 몇 개인지에 따라 결정된다. 그렇다면 우리는 2와 5의 개수가 몇 개나 들어 있는지 밝히는 코드를 짜야 될까? 그럴 필요는 없다. 왜냐하면 n! 에 들어 있는 5의 개수는 반드시 2의 개수보다 적기 때문에 5의 개수만 세어주면 그것이 즉 뒷자리 0의 개수이기 때문이다!!

납득이 잘 되지 않다면 아래와 같은 과정을 생각해 보자.

 

팩토리얼을 구하는 과정은 다음과 같다.  n! = 1 * 2 * 3 * ... * (n-1) * n

1부터 n까지 연속적으로 곱셈의 결과가 팩토리얼임을 알 수 있다. 5의 배수는, 즉 5가 인수로 포함되어 있는 수는 5, 10, 15 .. 즉 출현 간격이 5이다. 하지만 2가 인수로 포함되어 있는 수는 2, 4, 6, 8 .. 즉 출현 간격이 2이다. 따라서 n! 에 들어 있는 인수 5의 개수는 반드시 2의 개수보다 적다. 

따라서 n! 에 들어 있는 인수 5의 개수를 세어주기만 하면 된다. 하지만 n! 을 직접 계산하기에는 앞서 봤듯이 우리가 다루고 있는 어떤 자료형이라도 오버플로우가 날 것이기 때문에 팩토리얼에 들어갈 인수 한 개씩 검사해 주자.

---

시도 1(Python)

import sys
n = int(sys.stdin.readline())
cnt_zero = 0
for i in range(5, n + 1, 5):
    while not i % 5:
        i /= 5
        cnt_zero += 1
print(cnt_zero)

<해석>  for문에서 n이하의 5의 배수만 i에 대입해 준다. 만약 i 가 5로 나누었을 때의 나머지가 0이면 i를 5로 나누어주고 cnt_zero를 1 증가시킨다. 여러모로 생각할 것이 많은 문제였다.

---

시도 2(C언어)

#include <stdio.h>

int cnt_zeroes(int n) {
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", cnt_zeroes(n));
    return 0;
}

파이썬과 별 다를 바 없었다..