1676번 - 팩토리얼 0의 개수

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

1676번 문제 및 조건

문제요약:

 -> N!을 계산하고 그 계산된 값에서 뒤에서부터 0이 몇 개 나타나는 지 계산하는 문제

 

해결방법:

 1) N!을 직접 계산하고 0의 개수를 센다.

     -> 이렇게 계산하는 것이 제일 간단하지만, 시간이 너무 오래 걸리고 숫자의 크기가 너무 커진다는 문제가 있다.

 

 2) 0의 개수는 N!을 소인수분해해서 2의 개수와 5의 개수 중 작은 수이다. 

     -> 2와 5를 곱하면 10이 되어서 뒤에 0이 생기므로, 큰 수 가 아니고 작은 수다.

 

소스코드:

#include <iostream>
long long int divide(long long int n, long long int d) {
    long long int res = 0;
    while (1) {
        if (n % d != 0) {
            break;
        }
        else {
            n /= d;
            res++;
        }
    }
    return res;
}
int main() {
    long long int n, i, five = 0, two = 0;
    std::cin >> n;
    for (i = 1; i <= n; i++) {
        five += divide(i, 5);
        two += divide(i, 2);
    }
    if (five > two) {
        printf("%d\n", two);
    }
    else {
        printf("%d\n", five);
    }
    return 0;
}
 
 

 

한줄평:

문제해결 2번과 같은 방식을 많이 알아야 할 것 같다.