[백준 - C#] 1676번 팩토리얼 0의 개수

문제링크

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

1676번: 팩토리얼 0의 개수

 

문제

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

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. N의 팩토리얼 값을 구했을 때 뒤에서부터 0이 아닌 값이 나올 때까지 0의 개수를 구해야합니다.
2. N의 값은 0보다 크거나 같고 500보다 작거나 같습니다.
3. 500 팩토리얼의 값은 엄청 큽니다.

이번 문제의 경우 팩토리얼 값을 다 계산해서 0의 갯수를 구하기엔 너무 값이 크기 때문에 규칙이 있을 거라고 생각했습니다.

https://ko.numberempire.com/factorialcalculator.php

해당 홈페이지에서 팩토리얼 계산기를 사용시 규칙을 찾을 수 있었는데,

 

5! 0이 1개 10!일때 0이 2개 15!일 때 0이 3개 20!일때 0이 4개 로 볼 수 있으며

25!는 6개 30!는 7개 35!는 8개로 확인 할 수 있습니다.

 

즉 5의 배수마다 0의 카운트 값이 증가 하지만 25의 경우 2개 증가하는 것을 확인해 볼 수 있었습니다.

여기서 찾은 규칙은 아래와 같습니다.

5 = 1개
5*5 = 25 = 2개
5*5*5 = 125 = 3개

하지만  5의 배수일 경우에 카운트를 누적해주는 식으로 풀이를 진행하여야 합니다.

그 말인 즉슨 

5!의 경우 5의 배수가 1개 ( 5 )

10!의 경우 5의 배수가 2개 ( 5, 10 )

15!의 경우 5의 배수가 3개 ( 5, 10, 15 )

25!의 경우 5의 배수가 5개 ( 5, 10, 15, 20, 25 ) 하지만 25의 경우 5*5로 0이 2개입니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
    int count = 0;
 
    for (int i = 1; i <= N; i++)
    {
        // 125의 배수 일경우 3개 추가
        if (i % 125 == 0)
        {
            count += 3;
            continue;
        }
 
        //// 25의 배수 일경우 2개 추가
        if (i % 25 == 0)
        {
            count += 2;
            continue;
        }
 
        // 5의 배수 일경우  1개 추가
        if (i % 5 == 0)
            count++;
    }
 
    writer.WriteLine(count);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.