[BAEKJOON] 백준 9693: 시파르 (C#)

문제 링크

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

 

 

문제

N이 주어졌을 때, N!/10M이 정수가 되는 M 중 가장 큰 것을 출력하시오.

 

 

입력

각 줄에 5 ≤ N ≤ 106인 N이 있다. 입력의 마지막에는 0이 주어진다.

 

 

출력

각 줄에 Case #x: M의 형태로 (x는 1부터 시작한다) 가장 큰 M을 출력한다.

 

 

 

통과한 답안

using System.Numerics;

namespace _9693
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int cnt = 1;
            while (true)
            {
                int N = int.Parse(Console.ReadLine());

                if (N == 0)
                {
                    return;
                }

                int answer = FindFact(N);

                Console.WriteLine($"Case #{cnt}: {answer}");

                cnt++;
            }
        }

        static int FindFact(int N)
        {
            int twoCnt = 0;
            int fiveCnt = 0;

            for (int i = 1; i <= N; i++)
            {
                int now = i;

                while (now % 2 == 0)
                {
                    twoCnt++;
                    now /= 2;
                }

                while (now % 5 == 0)
                {
                    fiveCnt++;
                    now /= 5;
                }
            }

            return Math.Min(twoCnt, fiveCnt);
        }
    }
}

 

정수 N이 주어졌을 때, N! / 10^M이 정수가 되는 가장 큰 M을 찾는 문제이다.

즉 다시 말해서 N!을 10으로 나눴을 때, 나머지가 발생하지 않는 가장 큰 M을 찾는 것이다.

 

따라서 아래와 같이 코드를 작성할 수 있지만,

int fact = Factorial(N);

while (fact % 10 == 0)
{
    cnt++;
    fact /= 10;
}

 

이렇게 작성하면 시간초과가 발생하게 된다.

 

따라서 이를 해결하기 위해서 N!이 10의 배수가 되는 경우를 찾아보면,

2와 5를 곱하는 경우에 10의 배수가 되게 되므로

N!을 소인수 분해하여 2의 개수와 5의 개수를 구한 후에

그 중에서 작은 값이 10의 개수가 몇 개인지 결정하게 된다.

 

따라서 위의 코드와 같이 1부터 N까지의 숫자 중에서

2의 개수와 5의 개수를 저장하고

이 수 중에서 작은 값을 결과로 출력하면 문제를 해결할 수 있다.