문 제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입 력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

10

3

출 력

첫째 줄에 구한 0의 개수를 출력한다.

2

0

코 드

아래와 같이 풀었더니 N 숫자가 커질 시 자료형 자리를 초과해 버리는 문제 발생..

using System;
using static System.Console;
using System.Linq;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong N = ulong.Parse(ReadLine());

            string[] numbers = Factorial(N).ToString().Select(x => x.ToString()).ToArray();
            // string[] numbers = Array.ConvertAll(Factorial(N).ToString().ToArray(), x => x.ToString());
            ulong result = 0;

            for (int i = numbers.Length - 1; i >= 0; i--)
            {
                if (numbers[i] == "0")
                    result++;
                else
                    break;
            }

            WriteLine(result);
        }

        static ulong Factorial(ulong N)
        {
            if (N == 0)
                return 1;
            else
                return N * Factorial(N - 1);
        }
    }
}

비교코드 - 1

팩토리얼로 이용하여 풀면 자료형 범위도 넘어가고 효율적이지 않음.. (N이 15만 넘어가도)

결국 방법 모색중 ‘소인수분해’ 해법을 발견..

0이 생기는 경우는 5와 2가 곱해진 10이 존재하는 경우라 한다.

즉, 5의 개수를 구하면 된다!

using System;
using static System.Console;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(ReadLine());
            int result = 0;

            while (N >= 5)
            {
                result += N / 5;
                N = N / 5;
            }

            WriteLine(result);
        }
    }
}

공 부

c#에서 int형 배열을 string형 배열로 변환하는 방법!

1. Enumerable.Select (LINQ’s)

using System;
using System.Linq;

public class Example
{
    public static void Main()
    {
        int[] numbers = { 1, 2, 3, 4, 5 };

        string[] result = numbers.Select(i => i.ToString()).ToArray();
        Console.WriteLine(String.Join(", ", result));
    }
}

// 결과 : 1, 2, 3, 4, 5

1. Array.ConvertAll

using System;

public class Example
{
    public static void Main()
    {
        int[] numbers = { 1, 2, 3, 4, 5 };

        string[] result = Array.ConvertAll(numbers, x => x.ToString());
        Console.WriteLine(String.Join(", ", result));
    }
}

// 결과 : 1, 2, 3, 4, 5

소인수 분해

• ‘소수’인 ‘약수’로 나눈다.
• ‘몫’이 ‘소수’가 될 때까지 계속 나눈다.
• 나누어 준 소수들과 마지막 몫을 곱셈 기호로 연결한다. 이때 소인수분해한 결과는 보통 크기가 작은 소인수부터 차례대로 쓰고, 같은 소인수의 곱은 거듭제곱으로 나타낸다.

ex) 36 = 3 x 12 = 3 x 3 x 4 = 3 x 3 x 2 x 2 = 2^2 x 3^2