백준 1676번 (C#) - 팩토리얼 0의 개수

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

📌 문제 설명

N! (팩토리얼)을 계산했을 때, 그 수의 뒤에 있는 0의 개수를 구하는 문제다.

예를 들어 10! = 3628800 이면, 끝에 0이 2개 붙어 있으므로 정답은 2.

❓ 처음 접근

처음엔 문자열로 받아서 0의 개수를 세는 방법을 생각했다.
N!을 문자열로 바꾸고, 끝에서부터 0이 아닌 숫자가 나올 때까지 0의 개수를 세는 방식.

string input = Console.ReadLine();
List<char> list = new List<char>(input);
int count = 0;

for (int i = 0; i < list.Count; i++)
{
    if (i == 0 && list[0] == '0')
        count++;
    if (list[i] == '0')
    {
        count = i + 1;
        break;
    }
}
Console.WriteLine(count);

하지만 이렇게 하면 팩토리얼 결과값 자체를 계산해야 하고,
N이 커질수록 자료형 한계를 초과해서 오버플로우가 발생할 수 있다.

✅ 수학적인 접근

팩토리얼의 끝에 0이 붙는 건 곱셈 과정에서 10 = 2 × 5가 만들어지기 때문.
하지만 2는 훨씬 자주 등장하므로, 5가 몇 번 등장하는지만 세면 된다

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

예: 30!

30 / 5 = 6      // 5의 배수 개수
30 / 25 = 1     // 25는 5 × 5 이므로 한 번 더 셈
총합 = 6 + 1 = 7

→ 즉, 30!의 뒤에는 0이 7개 붙는다.

최종 코드

using System;

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int count = 0;

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

            Console.WriteLine(count);
        }
    }
}

✍️ 배운 점

팩토리얼 결과값을 직접 계산하는 것보다, 수학적인 규칙을 활용하는 것이 훨씬 효율적이다.

곱셈에서 0이 생기는 원인을 추적해서 문제를 해결할 수 있다.

문제를 수학적으로 다시 바라보는 습관을 들이자.