[Review] BOJ 1676번 문제 - solution2 규칙

[taek0622]

BOJ 1676번 문제는 어떤 수 N의 팩토리얼을 구했을 때, 뒤에서부터 수를 셀 때 처음 0이 아닌 숫자가 나올 때까지의 0의 갯수를 구하는 문제이다.

해당 문제를 어떻게 풀어야할지 여러 고민을 하다가, 처음에 낸 답은 뒤에서부터 0이 나온 개수와, 그 외의 수를 나누어서 팩토리얼에 돌리는 방법이었다.
하지만, 이 솔루션은 억지로 답을 짜내기 위해 만든 것에 불과하여 새로운 답을 생각했고, 아래가 새로 생각한 답이다.

let N = Int(readLine()!)!

print(N/5 + N/25 + N/125)

상당히 간결하고 별거 없어보여서 오히려 이것이 짜맞춘 답으로 보일 수 있지만 규칙은 다음과 같다.
예를 들어 5!을 구한다고 생각하면 5! = 5 * 4 * 3 * 2 * 1 = 120으로 0이 아닌 숫자가 나올 때까지 0의 개수는 1개이다.
10!을 구한다고 생각하면 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800으로 0이 아닌 숫자가 나올 때까지 0의 개수는 2개이다.

이렇게 구해본 후 한가지 특이한 점을 발견했다. 바로 0~95의 숫자의 팩토리얼에서는 5의 배수를 기준으로 0이 한개씩 늘어난다는 것이었다.
하지만 이 규칙은 100 이후의 수부터는 깨지게 되는데, 그래서 이 규칙을 어떻게 발전시킬 수 있을까 고민했다.

여기서 새롭게 발견할 수 있었던 것은, 팩토리얼 안에서 10이 얼마나 나오느냐에 따라서 0의 개수가 정해진다는 것이었다.
5!을 보면 5 * 4 * 3 * 2 * 1이므로 5 * 2 = 10. 즉, 10이 한번 나오므로 0이 1개이다.
10!을 보면 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1이므로 10 * 5 * 2 = 100 = 10 * 10. 즉, 10이 두번 나오므로 0이 2개이다.

하지만, 이렇게 10의 배수의 개수만 센다면 기존의 5의 배수의 개수를 센 것과 크게 다르지 않았다.
그래서 이 방법을 기준으로 새로 생각한 것이, 5의 제곱, 세제곱의 개수를 세는 것이었다.

100!을 구한다고 생각하면, 25 * 4는 100으로 0이 2개 추가되지만, 기존의 5의 배수를 카운팅 하는 방법으로는 1개만 카운팅 된다.
그러므로 5의 배수만 카운팅하는 것이 아니라, 5의 제곱인 25, 그리고 팩토리얼의 범위가 500까지이니 5의 세제곱인 125까지 카운팅하기로 했다.

그래서 나온 새로운 식이 N/5 + N/25 + N/125이다.
해당 방법으로 500!까지의 수에서 정상적으로 0의 개수를 구할 수 있었다.