백준 1676번 : 팩토리얼 0의 개수 (C++)

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

문제

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

 

코드

#include <iostream>
using namespace std;
int main() {
    int zero = 0;
    int n;
    cin >> n;
    for (int i=5; i<=n; i*=5)
    {
        zero += n/i;
    }
    cout << zero;
    return 0;
}

 

풀이

n을 입력받고 1~n까지의 곱(팩토리얼)의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지의 0의 개수를 구하는 문제인데 어떤 수 A에 곱셈 후 뒤에 0이 하나 더 생기려면 10을 곱해줘야 한다. 10은 2 X 5이므로 1부터 입력받은 n까지를 소인수 분해하여 2 X 5쌍이 몇 개 나오는지 구하면 0의 개수를 알 수 있다.

1부터 n까지의 값을 소인수 분해했을 때 2와 5가 몇 개 나오는지를 구하여야 하는데 이는 n을 2나 5로 나누어보면 알 수 있다. n을 100으로 생각하고 100 / 5 연산을 해보면 값은 20이 나온다. 이는 5 X 1, 5 X 2, 5 X 3, 5 X 4……. 5 X 20까지가 100보다 낮거나 같다는 말이 된다.

25 X 3을 보면 5 X 5 X 3과 같다는 것을 알 수 있다. 25 X 3 = 75 는 5 X 15이고 100 / 5를 수행했을 때 5 X 15의 5가 5의 개수로 카운트된다. 15는 5 X 3 이기 때문에 하나의 5가 더 있는데 이를 카운트 하기 위하여 5 X 5의 25로 100 / 25를 하여서 값 4를 얻을 수 있고 이는 25 X 1, 25 X 2, 25 X 3, 25 X 4 이 100보다 낮거나 같다는걸 알 수 있다. 5 X 5 X 5는 125이고 이는 100보다 커지게 된다. 그 말은 1부터 100까지의 수를 소인수 분해했을 때. 5,5,5를 포함하는 수가 없다는 말이다. 즉 값은 (100 / 5) + (100 / 25) = 24가 된다.

코드 7행을 보면 n을 기준으로 5로 나눈 값,5 * 5 로 나눈값 * 5 * 5로 나눈 값을 반복하다가 5가 계속 곱해진 값이 n보다 작거나 같을 때 까지 수행하는 코드인데 이는 소인수분해 했을 때 5가 몇 개 나오는지를 구하게 된다. 2가 몇 개 나오는지 구하는 코드는 없는데 이유는 팩토리얼은 1부터 n까지의 수를 곱하는 것이고 1부터 n까지의 수중 절반가량은 짝수일 것일 것이다. 짝수는 소인수 분해했을 때 2를 무조건 포함하게 된다. 따라서 5의 개수가 2의 개수보다 작을 수 밖에 없고 5의 개수를 세어주면 2X5 쌍의 수를 구할 수 있다.