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

문제 링크

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

 

 

문제

N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오.

예를 들어, 4! = 24 이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5! = 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2 이다.

 

 

입력

첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다.

 

 

출력

첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다.

 

 

 

통과한 답안

namespace _2553
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            long number = 1;
            for (int i = 1; i <= n; i++)
            {
                number *= i;

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

                number %= 100000000;
            }

            int answer =  (int)number % 10;


            Console.WriteLine(answer);
        }
    }
}

 

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

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

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

 

따라서 이 문제를 해결하기 위해서 생각한 아이디어는

팩토리얼을 계산하면서 뒷자리가 0이면 0을 제거하고,

앞자리의 숫자의 제한을 두어서 곱셈의 연산 속도와 정확성을 유지하는 것이다.

 

주어진 n 값에 대해서 1부터 n까지 곱하면서 결괏값을 number에 저장하는데

number이 10으로 나누어 떨어지면 나누어서 마지막 숫자를 0이 아니게 유지하고,

자리수가 8자리로 유지되도록 number를 100000000으로 나눈 나머지를 취하도록 하였다.

 

10으로 나누는 과정은 답을 찾기 위한 과정을,

100000000으로 나누는 과정은 숫자의 크기를 유지해 시간 초과의 발생을 방지한 것이다.