[c++] 백준 1676 - 팩토리얼 0의 개수

0. 주어진 문제

팩토리얼 0의 개수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10675	4688	3943	46.225%

문제

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

입력

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

출력

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

예제 입력 1 

10

예제 출력 1 

2

1. 풀이

뒤에 0이 등장하는 조건을 생각해보면, 팩토리얼에 포함된 10의 제곱의 개수만큼 0이 등장하게 될 것이다.

다시 정리하자면, 에서 x의 개수를 찾아내는 것이 핵심이다.

이때, x의 개수는 n!을 소인수분해하여 나온 5의 개수와 동일하다.(왜냐하면, 1~10까지 예를 들자면, 5는 5, 10에서 2번 들어가는 반면, 2는 2, 4, 6, 8,10일때 모두 포함되므로, 5의 개수만 카운팅 해도 무관)

따라서, 구현은 n!이 주어졌을때, 1~n까지 수를 (mod 5)를 하여 0이 나온 경우를 카운트 하는 형식으로 만들어 보았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<iostream>   int count_factorial(int n) {     int count = 0;     for (int i = 1; i <= n; i++) {         int temp=i;         while (temp % 5 == 0&&temp > 0) {             count++;             temp /= 5;         }       }     return count; }   int main() {     int N;     std::cin >> N;     std::cout << count_factorial(N) << std::endl; } Colored by Color Scripter

cs

3. 문제 출처

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

4. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.