JArchive 프로그래밍 일기

문제

팩토리얼 0의 개수 백준 1676번

리뷰

숫자 뒤 쪽에 0의 개수가 몇개가 되냐는건 소인수분해 했을 때 10이 몇번 곱해졌느냐에 따라 결정된다.

예를 들어, (팩토리얼 값은 아니지만) 34200 는 10이 2번 곱해진 것이다. 따라서 답은 2다. 2059000은 답이 3이다.

그런데, 10은 2x5 이다.

주어진 N을 5로 계속 나누는데, 나누어 떨어지는 개수를 세면 된다. == N! 을 소인수분해 했을때 5가 몇 승일까.

2의 개수를 안세도 되는 이유

10은 2x5니까 2의 개수도 세야 하지 않을까? 했다.
하지만, 소인수분해 했을 때 2를 인수로 가진 수의 개수 보다는, 5를 인수로 가진 수의 개수가 훨씬 적다.

7 팩토리얼을 예로 든다. 

7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 

5의 배수는 딱 1개 
2의 배수는 3개 (2,4,6) 

예를 들어, 125 팩토리얼을 구한다

5 * 25 * 125 까지만 곱해봐도 5로 나누어 떨어지는 것의 개수를 셀 수 있다.

125!

125/5 =>  25개
25/5  =>  5개
5/5  =>  1개
따라서 답은 31이 된다. 

따라서 반복문의 i는 5씩 곱하면서 증가시킨다.

KSJ14님의 해설을 읽고 도움받았다.

코드

#include <iostream> 
using namespace std;

int main(void){
     int N = 0;
    int cnt = 0;

     cin >> N;

    for(int i = 5; i <= N; i *= 5){
        cnt += (N/i);
    }

    cout << cnt;

    return 0;    
}