[BOJ][C++] 백준 1676번: 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

문제

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

입력

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

출력

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

 

풀이

1에서 n까지 수들의 5의 인수의 갯수를 구하면 된다 

원래는 인수가 2와 5일때의 갯수를 각각 구해서 더 적은 갯수를 리턴하면 되지만,

절대적으로 인수 2 의 갯수가 인수 5의 갯수보다 많으므로 인수 5의 갯수만 리턴한다

 

참고로 95%에서 틀리면 n=0인 경우를 생각하자

0! = 1 이기 떄문에 답은 0이다

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    int five=0, temp; // five: n의 인수 중 5의 갯수
    for(int i=1; i<=n; i++) {
        temp = i;
        while(temp%5 == 0) {
            temp /= 5;
            five++;
        }
    }
    
    cout << five;
    
    return 0;
}