[BaekJoon 1676][⚪5] 팩토리얼 0의 개수

❓ 문제

백준 1676 - “팩토리얼 0의 개수”

🎯 난이도

Silver ⚪5

🧠 풀이

1. 내 풀이 (수학)

- 알고리즘

• Mathematics

- 설명

필요한 숫자의 갯수를 세는 방식으로 푸는 풀이이다.

개인적으로는 생각보다 어려웠던 문제였다. (나는 수학쪽이 약한가..??) 일단 이 문제를 풀기 위해선 수학적으로 접근할 필요가 있다. 그 과정을 순서대로 정리하면 다음과 같다.

1. 뒤에 0이 추가되기 위해선 10이란 숫자가 곱해져야 한다.
2. 10은 2와 5의 곱으로 나눠질 수 있다.
3. 전체적인 숫자들을 인수 분해했을 때 2의 갯수는 5의 갯수보다 확실히 많다.
4. 따라서 5의 갯수를 세면 10의 갯수를 셀 수 있고, 이는 뒤에 붙는 0의 갯수와 같다.

이러한 흐름인데, 나는 미처 이 생각을 하지 못했다.

그럼 이제 5의 갯수를 세면 되는데, 어떻게 셀까? 그건 간단하다. 바로 N / 5이다. 왜 그럴까?

1. 1, 2, 3, 4 ... N 일 때, 특정 숫자 A의 갯수를 구한다 해보자.
2. N = 10이라 하면, 5의 배수는 5, 10이 있다. 이는 10 / 5 = 2와 같다.
3. N = 24라 하면, 5의 배수는 5, 10, 15, 20이 있다. 이는 24 / 5 = 4와 같다.

이런 식으로 특정 숫자가 일정 범위 내에서 몇 개나 존재하는 지를 쉽게 알 수 있다.

하지만 주의점도 존재한다. 바로 25, 125 같은 5의 거듭제곱으로 나눈 숫자도 더해주어야 한다는 것이다. 왜냐하면, 이러한 거듭제곱의 숫자들은 해당 숫자가 하나씩 더 들어가므로, 따로 또 더해주어야하는 것이다.

따라서 결과적으로 N까지의 5의 갯수는 최종적으로 다음과 같다.

\[\sum_{k = 1}^{\infty} \left[ \frac{N}{5^{k}} \right]\]

각 거듭제곱은 N을 넘지 않도록 해서 위의 공식을 사용해 5의 갯수를 구하면 끝이다.

5^k ≤ N 이므로 시간 복잡도는 O(log N)이다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    int iResult{};

    // 5의 배수로 나누며 5의 갯수 찾기
    for(int i = 5; i <= iN; i *= 5)
    {
        iResult += iN / i;
    }

    cout << iResult;

    return 0;
}

---

💭 후기

이런 문제는 수학적으로 접근해서 푸는 문제이다. 처음엔 맨 뒤의 숫자가 0이 될때마다 나누기, 나머지 계산을 섞어가며 세는 방식으로 했는데 예외 상황에서는 제대로 값을 구하지 못했다.

특정 숫자의 갯수를 '범위 내'에서 세는 방법을 알아가는 좋은 문제였던 것 같다.