[백준(BOJ)] 1676 팩토리얼 0의 개수 C++

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

아래와 같이 풀었는데, 시간 초과가 떴다.

#include <iostream>

using namespace std;

int main(){
    // 첫째 줄에 N(0 ≤ N ≤ 500)이 주어진다.
    int N;
    cin >> N;
    // 팩토리얼 저장
    long long factorial[N+1];
    factorial[0]=1;
    factorial[1]=1;
    for (int i=2;i<=N;i++){
        factorial[i] = factorial[i-1]*i;
    }

    // N!을 NFac에 저장하고, 10으로 나누어 떨어지면 맨 뒤 숫자가 0이라는 뜻
    // 10으로 나눠주고 zeroNum을 1증가 시켜준다.
    long long NFac=factorial[N];
    int zeroNum =0;
    while (NFac%10==0){
        NFac/=10;
        zeroNum++;
    }

    // N!을 출력
    cout << zeroNum << '\\n';
    return 0;
}

[백준][C++] 1676: 팩토리얼 0의 개수 - 토르비욘

[백준] 알고리즘 C++ 1676번 - 팩토리얼 0의 개수문제

10=2*5라는 것을 이용해 푸는 문제였다.

팩토리얼 0의 개수 백준 1676번 c++ - 프로그래밍 일기

 

10은 2*5.

어떤 수를 소인수분해 했을 때, 2는 엄청 많이 나올 거고, 5는 그것보다 적게 나올 것이다.

그래서 5는 무조건 2랑 짝지어질 수 있다.

 => N!이 소인수분해 했을 때, 5가 몇 개 나오는지만 알면 뒤에 0이 몇 개 붙는지 알 수 있는 것이다.

 

10!의 0의 갯수를 세보자

1 → 5의 갯수:0

2 → 5의 갯수:0

3 → 5의 갯수:0

4 =2*2 → 5의 갯수:0

5 → 5의 갯수:1

6 =2*3 → 5의 갯수:0

7 → 5의 갯수:0

8 =2*2*2 → 5의 갯수:0

9 =3*3 → 5의 갯수:0

10 =2*5 → 5의 갯수:1

5의 갯수가 총 2개이므로 맨 뒤에 붙는 0의 갯수는 2개가 된다.

 

구글링하면 아래처럼 코드를 짠 사람이 많았는데, 왜 이게 작동하는지 궁금했다.

for (int i = 5; i <= n; i *= 5) {
		ans += n / i;
	}

🤔 궁금한 것

1. 왜 애초에 10으로 나누어 떨어지는 수를 구하지 않는 것인지 ⭐️⭐️⭐️
2. N!을 구하는데 ans += n / i; 왜 이렇게만 해도 되는 건지

10!의 0의 갯수를 구한다고 하면, n은 10이 된다.

ans += 10/5 ⇒ 2

 

여기까지 했을 때는 사실 알듯말듯 했다.

10은 5의 배수가 맞는데, 10에 들어가는 5의 갯수는 1개고, 10/5를 했는데 5의 배수인 5와 10이 카운트되는 게 뭔가 쉬운데 어렵게 느껴졌다. 그래서 좀 더 말을 쉽게 바꿔서 아래와 같이 생각해봤다.

 

100까지의 수 중 5의 배수가 몇 개 있는지.

    5, 10, 15, 20, 25, 30, … , 95, 100 → 20개 = 100/5

25 = 5*5 = 5^2 5가 2번 들어간다고 카운트해야한다.

5가 들어간 것을. ans += n/5로 모두 카운트 한 후, i*=5로 5가 2번 들어간 애들은 한 번 더 카운트 ans += n/25

    25, 50, 75, 100 → 4개 = 100/25

100!에서 뒷자리 0의 갯수는 20+4= 24개가 된다.

100!은 실제로 다음과 같다.

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

 

+)만약 n이 125보다 크다면, 125=555 =5^3 한 번 더 카운트 해야한다.

ans += n/5

ans += n/25

ans += n/125

625(=5^4)는 문제에 주어진 N의 범위(0 ≤ N ≤ 500)를 초과하기 때문에 반복문은 최대 3번만 돌아간다.