백준_1676_팩토리얼0의개수

 

 

팩토리얼에서 맨 뒤에서부터 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제입니다.

 

문제가 잘 이해가 안되실 수 있으니 (제가 그랬습니다..) 예시를 보여드리겠습니다.

 

5! = 5*4*3*2*1 = 120 -> 1개

 

6! = 6*5*4*3*2*1 = 720 -> 1개

 

7! =  7*6*5*4*3*2*1 = 5040 -> 1개

 

8! =  8*7*6*5*4*3*2*1 = 40320 -> 1개

 

9! =  9*8*7*6*5*4*3*2*1 = 362880 -> 1개

 

10! = 10*9*8*7*6*5*4*3*2*1  = 3628800 -> 2개

어떤 숫자의 맨 뒤에 0이 오기 위해서는 반드시 10이 곱해져야 합니다.

10 = 2*5 이므로, 2와 5의 개수를 찾으면 0의 개수 또한 구할 수 있겠죠.

 

하지만, 여기서 생각해봐야 할게 한가지 더 있습니다.

 

굳이 2의 개수를 세야 할까? 라는 의문입니다.

 

4=2^2 , 8=2^2  . . . . 이와 같이 2의 거듭제곱꼴은 많고도 많습니다.

 

5의 개수와 비교하자면 훨씬 말이죠.

 

그럼 5의 개수만 세면 2의 개수는 충분하니 자동으로 10이 되게 할 수 있지 않을까요?

 

따라서 저희는 5의 개수만 찾으면 됩니다.

 

위 예시에서도 볼 수 있듯, 5의 개수(5의 배수의 개수 포함)가 뒤의 0의 개수와 일치하다는 것을 확인할 수 있습니다.

 

그럼 이 규칙이 큰 숫자에서도 적용될까요?

 

25! = 15511210043330985984000000

으로 뒤에 0이 6개입니다. 왜 그럴까요?

25 는 5의 거듭제곱꼴이기 때문입니다. 

따라서, 뒤에 0이 몇개인지 구하기 위해서는 5의 배수뿐 아니라 5의 거듭제곱의 배수가 몇개 있는지 세주면 됩니다.

 

 

 

전체 코드)

#include <stdio.h>

int main(void)
{
    int N = 0;
    scanf("%d", &N);

    int count = 0;
    for (int i = N; i >= 1; i--)
    {
        if (i % 5 == 0)
        {
            count++;
        }

        if (i % 25 == 0)
        {
            count++;
        }

        if (i % 125 == 0)
        {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}