백준 C# - 1676 +) 풀이

서론

처음에 풀때 팩토리얼 계산을 이용해서 풀었다. 효율적이지 않은 것 같아서 인터넷을 찾아보니 5와 2의 소인수분해로 풀어야 된다는 것을 알게되었다.

---

풀이

5의 개수를 구하자

0이 생기는 경우는 5와 2가 곱해진 10이 존재하는 경우이다. 따라서 5와 2의 갯수를 구해야 한다. 

팩토리얼 특성상 5가 있으면 2가 존재하므로 5의 갯수만 구하면 된다.

while (n >= 5)
{
    zeroCount += n / 5;
    n /= 5;
}

예를 들어서

10이면 10/5이므로 2개 된다.

25이면 25/5이므로 5개에서 반복문을 한 번 더 돌아서 5/5 1개가 또 더해져서 6이 된다.

---

코드 전문

using System;

namespace baek2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int zeroCount = 0;

            while (n >= 5)
            {
                zeroCount += n / 5;
                n /= 5;
            }
            Console.WriteLine(zeroCount);
        }
    }
}