알고리즘 스터디 - 백준 1676번 : 팩토리얼 0의 개수

문제 해석

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

?? 무슨말일까? 예시를 살펴보자

1) 10!

• 10x9x8x7x6x5x4x3x2x1이고 뒤에서부터라고 하니까 1x2x3x4x5x6x7x8x9x10인데 0이 아니 수를 어떻게 알아?
• 해서 찾아보니 식에서 확보하는 것이 아니고 계산된 값에서 찾는 것이다.

2) 3!

• 6으로 0이 없다.

어떤 알고리즘을 써야할까?

0이 나오는 케이스를 찾아야 한다.

우리가 숫자를 다루고 식을 다루다 보면 사실 10의 개수가 0의 개수라고 볼 수 있다. 근데 더 작은 케이스로 나누다 보면 5의 개수가 0의 개수를 좌지우지 한다는 것을 알 수 있다.

10 = 5 x 2로 구성 되어 있는데 2는 사실 모든 팩토리얼에서 많이 나오기 때문에 2를 배제할 수 있다.

N의 최대 값이 500으로 5가 나오는 몫을 계산하면 된다.

알고리즘 코드

N = int(input())

num = 0

while N >= 5:
    num += N // 5

    N //= 5

print(num)