[BAEKJOON] 백준 7489: 팩토리얼 (C#)

문제 링크

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

 

 

문제

n!은 정수 n에 대한 팩토리얼 수를 나타내는데, 이는 1부터 n까지의 모든 정수의 곱을 의미한다. 팩토리얼은 굉장히 빨리 커지기 때문에 13!는 대부분의 컴퓨터에서 32비트 정수형을, 70!은 대부분의 부동 소수점 변수의 범위를 넘어선다. 우리는 n!에 대하여 0이 아닌 최우측 수(the rightmost non-zero digit)를 찾으려고 한다. 예를 들어, 5! = 1 * 2 * 3 * 4 * 5 = 120 이므로 5!의 최우측 0이 아닌 수는 2이다. 마찬가지로 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040이며 7!의 0이 아닌 최우측 수는 4가 된다.

 

 

입력

첫 줄에 테스트 케이스의 수 t ( 0 < t < 15)가 주어진다. 연속하여 t개의 줄에는 정수 n이 하나씩 주어진다. ( 0 < n < 1001).

 

 

출력

n!의 최우측 0이 아닌 수(the rightmost non-zero digit)를 출력하시오.

 

 

 

통과한 답안

using System.Text;

namespace _7489
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(Console.ReadLine());
                int answer = (int)FindFactorial(n);
                sb.AppendLine(answer.ToString());
            }

            Console.WriteLine(sb.ToString());
        }

        static double FindFactorial(int n)
        {
            long number = 1;
            for (int i = 1; i <= n; i++)
            {
                number *= i;

                while (number % 10 == 0)
                {
                    number /= 10;
                }

                number %= 10000;
            }

            return number % 10;
        }
    }
}

 

주어진 숫자에 n을 팩토리얼 한 결과의 수에서 0이 아닌 가장 낮은 자리 수를 구하는 문제이다.

팩토리얼은 n이 주어졌을 때, 1부터 n을 곱한 결과로

숫자가 매우 커지는 경향이 있어서 int나 long으로도 처리할 수 없는 경우가 많다.

 

이 문제도 이전의 2553 문제와 같은 방식으로 풀이하였는데,

https://lawrence1031.tistory.com/286

[BAEKJOON] 백준 2553: 마지막 팩토리얼 수 (C#)

 

주어진 n에 대해서 1부터 n까지 곱하는 과정을 number로 저장하는데,

number가 10의 배수이면 10으로 나눠주고

5자리가 넘어가는 경우에는 100000으로 나눠서 숫자의 범위를 제한했다.

(n의 범위가 1부터 1001이므로 100000로 제한이 가능하다)

 

또, 시간 초과가 발생하는 문제를 해결하기 위해 StringBuilder를 사용하여

출력을 한 번만 실행하도록 조정하였다.