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

백준 1676번 c++ 문제풀이

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

풀이:

이 문제는 팩토리얼을 구할 필요가 없다. 뒤에 0이 나오려면 10이 곱해져야 한다는 것만 알면 간단히 풀 수 있다. 10은 2*5로 만들 수 있다. 2의 배수와 5의 배수의 개수를 구하면 되는데, 2의 배수는 5의 배수보다 훨씬 자주 등장하므로 5의 배수의 개수만 구해주면 된다.

예를 들어 10!은 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 이다. 5의 배수는 5 와 10 두개이므로 뒤에 0이 총 두 개 붙는다는 것을 알 수 있다.

25의 배수 와 125의 배수도 구해 주어야한다. 25는 5가 두개이고 125는 5가 세 개이기 때문이다.

25!로 예를 들어 보자, 5의 배수가 총 5개, 25의 배수가 1개이다. 따라서 뒤에 0이 총 6개 붙는다. 25는 5가 두개 들어있는 거지만, 5의 배수에서 이미 25도 한번 카운트를 했기에 중복해서 셀 필요가 없다는 것을 알 수 있다. 125도 총 5가 세개이지만 5의 배수와 25의 배수 개수 셀 때 이미 세어지기에 중복할 필요가 없다.

따라서 N을 입력 받고 5, 25, 125로 나눈 값들을 더해주면 된다.

코드:

#include <iostream>

using namespace std;

int main(){

    int n;
    cin >> n;
    int count = 0;
    
    count += (n/5);
    count += (n/25);
    count += (n/125);


    cout << count;
    return 0;
}

처음 문제를 풀 때 계속 팩토리얼을 재귀로 구현해서 풀었는데, 숫자가 커질수록 시간 초과가 되어 문제 푸는데 조금 헤멨던 것 같다. 하지만 문제의 요점이 5의 배수의 개수를 세는 거라는 것만 파악한다면 굉장히 간단한 코드로 답을 구할 수 있다는 것을 알 수 있다.