[C++] 백준 1676번 : 팩토리얼 0의 개수

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

팩토리얼 0의 개수문제

 

🎨 코드

 

#include<iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    int count = 0;

    for (int i = 5; i <= N; i *= 5) {
        count += N / i;
    }
    cout << count << endl;

    return 0;
}

 

🎯 풀이

 

문제 팩토리얼 0의 개수는 팩토리얼의 결과로 나오는 값의 뒤에 0이 몇 개 붙어있는지 알아내는 문제이다.

만약 팩토리얼의 결과로 xxxx000이 나오면 3을 출력하고 xxx0x00이 나오면 2를 출력하는 방식이다.

 

팩토리얼을 하나하나 계산하는 방식으로 풀 수 있지만 너무 비효율 적이다.

 

0이 몇 개 인지 알아내기위해 N! 를 소인수 분해했을 때, 2와 5가 몇 개 나오는지 알면 되는데,

5의 개수가 항상 2의 개수 보다 적기 때문에, 5의 개수만 세어주면 됩니다.

 

5의 개수는 입력된 값을 5로 나누어보면 됩니다.

 

만약 100!이 입력된다면, 100 / 5로 20이 나오고, 5가 중복되는 25, 50, 75, 100까지 총 4개

합은 24가 나오는 방식입니다.

 

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

 

위 반복문을 통해 N / i를 한 값을 count에 더해주고 

i를 5 곱해줍니다.

 

첫 반복때 100 / 5로  count에는 20이 들어갑니다.

두 번째 반복 때 100 / 25로 count에는 24가 들어갑니다.

 

결과적으로 정답은 24가 됩니다.