백준 1676 : 팩토리얼 0의 개수

처음에는 아래와 같이 별 생각없이 풀긴 했다.

 

N = int(input())
if N:
    for i in range(N - 1, 1, -1):
        N *= i
    N = str(N)[::-1]
    cnt = 0
    for i in N:
        if not int(i):
            cnt += 1
        else:
            break
    print(cnt)
else:
    print(0)

 

다만 이것은 파이썬이라 풀리는 방법이고,

아마 다른 언어였으면 오버플로우가 발생해서 풀지 못했을 것이다.

 

다른 사람은 아래와 같이 풀었다.

 

n = int(input())
def five_count(n):
    cnt = 0
    while n != 0:
        n //= 5
        cnt += n
    return cnt
    
print(five_count(n))

 

왜 5로 나눴을까? 에 대해서 생각하다보니 글이 조금 글어졌다.

---

우선, 10!의 경우 3628800이고 뒤에 0이 두개 있다.

이는 36288 * 10^2로 나타낼 수 있다.

 

즉, 0의 개수를 구하려면 뒤에 0이 없어질때까지 10으로 나누면 되고,

10!을 10으로 나눈 횟수 두 번이 바로 뒤의 0의 개수인데,

모든 수를 팩토리얼한 다음 10으로 나누려고 하면 고민했던 바와 같이 수의 크기 때문에 오버플로우가 발생한다.

그래서 10!을 계산하기 전의 과정에서 답을 구해야 하는데,

 

일단 10!을 풀어보면,

10 * 9 * 8 ... 2 * 1이다.

 

아까 0이 없어질때까지 10으로 나누면 된다고 했으니까, 여기서 10이 몇 번 곱해지는지 보면 될 것이다.

 

10을 찾아보면 맨 앞에 하나 있고, 중간에 있을 5와 2의 곱으로도 10을 만들 수 있다.

결과적으로 10이 두 번 곱해지는 것을 알 수 있다.

 

이제 이 나열된 10 * 9 * 8 ... 2 * 1 에서 나머지 힌트를 찾아야 하는데,

5와 2의 곱으로도 10을 만들 수 있다고 했으니 이것을 10!을 풀어놓은 것에 넣어서 아래와 같이 다시 써볼 수 있다.

 

10 * 9 * 8 ... 2 * 1

= (5 * 2) * 9 * 8 * 7 * 6 * (5 * 2) * 4 * 3 * 1

 

위처럼 10의 위치에 5 * 2가 들어가 있는 것을 볼 수 있다.

이것을 다음과 같이 다시 쓸 수 있다.

 

= 9 * 8 * 7 * 6 * (5^2) * 4 * 3 * (2^2) * 1

 

이와 같이 10의 약수는 1 * 2 * 5 인데 이 말은, 10의 개수를 찾는다는 것이 5나 2가 몇 번 곱해져 있는지 찾는다는 것과 같다고 볼 수 있다.

 

즉, 위의 10에 해당하는 괄호에서 2를 선택하든 5를 선택하든 둘 중 하나를 선택해서 그것이 전체적으로 몇 번 곱해져 있거나 약수의 형태로 포함되어 있는지 개수를 세면 되는데,

2는 10을 제외하고도 모든 짝수의 약수에도 해당되기 때문에(4, 6, 8에도 2가 곱해져 있으므로 2를 선택한다는 것이 곧 10

이라고 확신할 수 없다), 5의 개수를 찾는 것이 결과적으로 10의 개수를 찾는것과 같은 효과가 있다.

 

그러면 이제 5를 찾으면 된다는 것까지 알았다.

이제 10!을 풀어 놓은 것을 보면 10 ~ 1까지 필요한 모든 수가 곱해져 있을 텐데,

 

그 중에서 5가 포함되는 수의 개수를 찾으면 그것이 정답이 된다.

왜냐하면 그 수들은 어차피 모두 곱해질 수들이기 때문에,

곱하기 바로 전 단계에서 1부터 10까지 5로 나누어 떨어지는 수가 몇 개인지 미리 찾아놓으면 된다.

 

즉, 10을 5로 나눴을 때 몫 2가 해당 문제의 정답이 된다.

 

17!의 경우를 보면,

 

17에서 5를 나눈다는 의미는,

17!은 17 ~ 1까지 모든 수를 곱한다는 것이기 때문에 그 수들 중에서 5로 나누어떨어지는 것의 개수를 찾으면 된다.

 

나누면 몫은 3이 나오고, 17!의 값은 355,687,428,096,000으로 뒤에 0이 3개가 오는 것을 확인할 수 있다.