[백준 1676] 알고리즘 23일차 : 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

수학3 c++

접근방법

애초에 팩토리얼 구하는 수의 범위가 500까지라(시간제한2초) 팩토리얼을 계산해서 푸는 문제는 아니었다.

가장 작은 자리 수 부터 연속되는 0의 개수를 출력하는 문제라

N부터 0까지 연속되는 수가 모두 곱해서 팩토리얼 결과가 나오는 거니까

0의 개수는 5*2의 개수이다.

근데 연속되는 수니까 2의 개수가 5의 개수의 비해 많을게 분명하다.

따라서 2의 개수는 세지 않고 5의 개수만 센다.

이때 주의할 점은 25, 125같이 2개 이상의 5로 구성된(?)수가 있어서

하나의 수를 5로 나눠질때까지 계속 나눠서 카운트한다. (그래서 변수 k를 하나 더 썼다.) 

끝!

 

맞았습니다

소스코드

#include <iostream>
using namespace std;
int main(){
    int n,k;
    cin >> n;
    int cnt = 0;
    for(int i = n ; i > 0 ; i--){
        k = i;
        while(k%5 == 0){
            cnt++;
            k = k/5;
        }
    }
    cout << cnt;
    return 0;
}