[01676] 팩토리얼 0의 개수

[01676] 팩토리얼 0의 개수

문제

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

입력

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

출력

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

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_N 500

/* 변수 */
int N;
int count = 0

/* 함수 */

int main() {
    /* 입력 */
    cin >> N;

    /* 풀이 */
    for(int i = 2, num; i <= N; i++) {
        num = i;
        while(num % 5 == 0) {
            num /= 5;
            count++;
        }
    }

    /* 출력 */
    cout << count << '\n';
}

풀이

논리

곱해서 뒤에 0이 나오려면 10의 배수여야 하며,
그 갯수는 곱해진 10의 개수와 같다.
10의 약수는 2, 5 두가지 이므로 곱해진 2와 5의 개수를 구해 둘 다 나온 숫자(두 수 중 작은 수가 될 것이다)가 곱해진 10의 개수이다.

그.런.데.
2만큼 증가할 때 마다 나오는 2보다 5만큼 증가할 때 마다 나오는 5가 확실히 적다.
따라서 2는 안세줘도 된다.

출처

백준 [01676] 팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676