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

해당 문제는 DP 알고리즘으로 풀었다.
물론, 이렇게 푸는 것 보다 소인수분해의 성질을 이용하면 쉽게 풀 수 있다고 하는데.

약간의 자존심? 때문에 어떻게든 DP로 풀어보겠다고 여러가지 시도를 해보면서 알아낸 것들을 적고자 한다.
1. C++에서 long long 타입은 20! 까지만 구할 수 있다.
물론 unsigned 시 65! 까지 구할 수 있지만 그 이후로는 불가능하다.

이를 해결하기 위해선 C++에선 따로, String으로 변환하고 자르고 붙이는 노가다를 해줘야 했고.
지원해주는 공식 라이브러리 조차 없다보니, 차후 이런 비슷한 문제가 나왔을 때 풀기가 너무 어려울거라 생각했다.

하여, BigInteger를 공식으로 지원하는 C#, JAVA 중 C#으로 구현해보았다.

using System;
using System.Diagnostics;
using System.Numerics;

    class Program
    {
        const int MAX = 501;
        public static BigInteger[] dp = new BigInteger[MAX];
        public static int N = 0;
        public static void Input()
        {
            N = int.Parse(Console.ReadLine());
        }

        public static void Solution()
        {
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= N; i++)
            {
                dp[i] = i * dp[i - 1];
            }
            int count = 0;
            string s = dp[N].ToString();
            for(int i = s.Length - 1; i >= 0; i--)
            {
               if (s[i] != '0') break; 
                count++;
            }
            Console.WriteLine(count);
        }

        public static void Solve()
        {
            Input();
            Solution();


        }

        public static void Main(string[] args)
        {
            Solve();
        }
    }

풀이는 간단하다. N만큼 DP에 담아두고, string으로 형변환 한 후, 길이의 마지막 부터 반복문을 돈다.
이는 문제에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
라 하였기에, 중간에 0이 들어가는 것은 계산해선 안되기 때문이라 볼 수 있다. 0을 만나면 그대로 포문을 빠져나오고 아니라면 count를 계속 1씩 증가 시킨 후 마지막에 출력해주면 된다.