N!의 뒤부터 연속되어 나타나는 0의 개수를 출력하는 문제입니다. 우선 수 뒤에 0이 붙는 조건을 생각해봅시다. 수 뒤에 0이 n개 붙는 것은 10n의 배수라는 것입니다. 이를 조금 다르게 쓰면, 소인수분해했을 때 2k×5l이 포함되어있을 때, k와 l중 작은 값만큼 0이 붙는 것이 됩니다. 23×55이면 3과 5중에 작은 값인 3만큼 0이 붙어있게 되는 것이죠. 이제 N!에 대한 경우를 알아보죠. N!의 몇 개의 예시를 살펴보면 소인수분해 했을 때 2k×5l 꼴이 나타나는데, k가 l보다 월등히 큰 값을 가집니다(증명은 아래에 따로 첨부합니다). 따라서 N!을 소인수분해했을 때 가지는 5의 거듭제곱이 몇인지 알면 그것이 결국 뒤에 붙는 0의 개수가 됩니다. 즉, 5의 지수의 개수를 구해야 하는데, 그 방법은 간단합니다. 5의 배수 개수를 세고, 52의 배수를 세고, … , 5k의 배수를 세는데, 5k 값이 N보다 작을 때까지 반복합니다. 이렇게 하면 되는 이유를 간단하게 설명하면, 1부터 N까지 칸이 있는데, 각 수마다 5의 몇 승인지를 블럭 개수로 표시한다고 합시다. 그러면 5, 10, 20 등에는 블럭 1개, 25나 50에는 블럭 2개가 놓일 것입니다. 이를 블럭을 쌓은 방향으로 세면 1, 1, 1, 1, 2, 1, 1, …와 같은 수열이 되지만 수가 증가하는 방향으로 쌓였다고 생각해보면 [N/5], [N/25], …이 됩니다. 아래 그림처럼 말이죠.
즉, N을 5로 나눈 몫을 구하고, N을 25로 나눈 몫을 구하고, …를 반복하면 됩니다.
증명
N!은 풀면 N×(N-1)×...×2×1이므로 N!을 소인수분해한 것은 1부터 N까지의 자연수의 소인수분해한 것을 모두 곱한 것과 같습니다. 여기서 2의 지수와 5의 지수가 무엇이 되는지를 비교합니다. 먼저 2의 지수는 1부터 N까지의 자연수 중 2의 배수, 22의 배수, ... 2k의 배수인 것을 각각 센 후 모두 더한 값입니다. 즉, 아래와 같이 됩니다.
$$
[\frac{n}{2}]+[\frac{n}{4}]+[\frac{n}{8}]+...\ge[\frac{n}{2}]\ge\frac{n-1}{2}
$$
위의 두 번째 부등식이 성립하는 이유는 n이 정수 범위이기 때문입니다.
마찬가지로 5의 지수를 구해보면 아래와 같습니다.
$$
[\frac{n}{5}]+[\frac{n}{25}]+[\frac{n}{125}]+...\le \frac{n}{5}+\frac{n}{25}+\frac{n}{125}+...=\frac{n}{4}
$$
그런데, n≥2일 때에 위의 두 식을 비교해보면,
$$
\frac{n-1}{2}-\frac{n}{4}=\frac{n-2}{4}\ge 0(n\ge 2)
$$
즉, 항상 2의 지수가 5의 지수보다 크거나 같습니다. 따라서 N!의 10의 지수를 구할 때에는 5의 지수가 몇인지만 보고 판단할 수 있습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-02 18:01:25 |