[백준] 2004 - 조합 0의 개수

1. 문제

2004번: 조합 0의 개수

2. 개요

nCm의 끝자리 0의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

nCm = n!/(n-m)!*m! 이다.

끝자리 0의 개수는 10의 몇배수냐에 따라 달라지고 10은 2와 5의 개수로 구할 수 있다.

nCm을 곱으로 나타냈을 때 2의 총 개수와 5의 총 개수 중 더 작은 수가 답이 된다.

위에서 나타낸 n!/(n-m)!*m! 을 이용하여 2의 개수와 5의 개수를 구하고 더 작은 값을 출력한다.

3-2. Python

import sys

n, m = map(int, sys.stdin.readline().split())

def counttwo(num):
    cnt = 0
    while num > 0:
        num = num // 2
        cnt += num

    return cnt

def countfive(num):
    cnt = 0
    while num > 0:
        num = num // 5
        cnt += num

    return cnt

print(min(counttwo(n) - counttwo(n-m) - counttwo(m), countfive(n) - countfive(n-m) - countfive(m)))

3-3. C#

namespace boj_2004
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]), m = int.Parse(input[1]);

            Console.WriteLine((int)MathF.Min(counttwo(n) - counttwo(n - m) - counttwo(m), countfive(n) - countfive(n - m) - countfive(m)));
        }

        static int counttwo(int num)
        {
            int cnt = 0;

            while (num > 0)
            {
                num = num / 2;
                cnt += num;
            }

            return cnt;
        }
        
        static int countfive(int num)
        {
            int cnt = 0;

            while (num > 0)
            {
                num = num / 5;
                cnt += num;
            }

            return cnt;
        }
    }
}