[C] 1676번: 팩토리얼 0의 개수

문제#

https://www.acmicpc.net/problem/1676

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

입력#

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력#

첫째 줄에 구한 0의 개수를 출력한다.

풀이#

팩토리얼의 뒤에 붙는 0은 10 = 2 × 5 가 만들어질 때마다 하나씩 생깁니다.

팩토리얼에서는 2의 개수는 충분히 많고, 5의 개수가 부족하므로 5가 몇 개 들어 있는지만 세면 됩니다.

예를 들어

• 5는 5가 1개
• 10도 $2 * 5$ 5가 1개
• 15도 $3 * 5$ 5가 1개
• 25는 $5 * 5$ 이므로 5를 2개 제공

따라서 답은

를 모두 더한 값입니다.

코드#

1
#include <stdio.h>
2

3
int main() {
4
    int n;
5
    int count = 0;
6

7
    scanf("%d", &n);
8

9
    while (n >= 5) {
10
        count += n / 5;
11
        n /= 5;
12
    }
13

14
    printf("%d\n", count);
15
    return 0;
16
}