[1676번] 팩토리얼 0의 개수

문제 출처 :

 

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

알고리즘 분석 :

간단하게 설명하고자 한다.

이 문제는 n!을 할 때 끝자리 0이 몇개 나오는지 묻는 문제이다.

잘 생각해보자.

2와 5가 곱해지면 10이 된다.

2 2 와 5 5 가 곱해지면 100이된다.

2 5 2 5 2 5가 곱해지면 1000이 된다.

따라서 우리는 2와 5의 개수를 n! 내에서 세면 된다.

그때의 2와 5의 개수 중 더 작은 값이 정답이 된다.

예를들어 2 2 2 5 5면 200이기에 0은 2개이고, 정답은 5가 2개이기에 답은 2이다.

자세히 생각해보면 어떤 수 n!에 대해 2와 5의 개수는 항상 5가 작음을 알 수 있다.

따라서 이 문제는 n!에서의 5의 개수를 세는 것과 같아진다.

#include <iostream>
#include <cstdio>
 
#define min(a,b)(a < b ? a : b)
 
using namespace std;
 
int main()
{
    int n, tmp;
    scanf("%d", &n);
 
    int two = 0, five = 0;
    for (int i = 1; i <= n; i++)
    {
        tmp = i;
        while (tmp)
        {
            if (tmp % 2 == 0)
            {
                two++;
                tmp /= 2;
            }
            else
                break;
        }
 
        tmp = i;
        while (tmp)
        {
            if (tmp % 5 == 0)
            {
                five++;
                tmp /= 5;
            }
            else
                break;
        }
    }
 
    printf("%d",min(two, five));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

따라서 이 문제는 n!에서의 5의 개수를 세는 것과 같아진다.

아래 내용은 몇년 전 내가 작성한 어리석은 알고리즘 해석 방법이다.

값이 500이상이 되어 10^8까지만 범위가 되도 아래 코드는 작동 할 수 없다.

문제 해결에 필요한 사항

1. 팩토리얼의 정의

2. 500!의 0의 개수 생각방법

3. 팩토리얼과 0의 관계

팩토리얼을 몇가지 확인해보면 다음과 같다.

20! = 2,432,902,008,176,640,000

10! = 3,628,800

즉, 이미 20!으로만 가도 long long int로도,  int로도 해결이 되지 않는다.

50!은 생각할 수 없을 정도로 클 것이기에 이 값을 다 구한다는것은 문제 해결에 어울리지 않는다.

팩토리얼을 자세히 보면 0이 생기는 부분에서 10으로 나누면 나머지가 0임을 확인 할 수 있다.

즉, 10!에서 10으로 2번 나누어지기에 0이 2번있는것이다.

그리고 0이 없이 값이 무수히 커질때는 다음과 같이한다.

예를들어 x!이 123,456,678,123,123이었다면 이것은 0이 없기에 또 long long int, int를 벗어나게 되는데

이때는 그냥 값이 대략 어림잡아 10만이 넘어가면 10만단위를 잘라주면 된다.

즉, 123,456이될때는 456만 남게해도 뒷자리가 더 곱해졌을 때 0이 생기는 것에 지장을 주지 않는다.

 

소스 코드 : 

#include <stdio.h>
 
 
int total = 1;
int cnt = 0;
 
 
int main()
{
 
    int n;
    int i = 1;
    int tmp;
    scanf("%d", &n);
 
    while (n >= i)
    {
        total = total * i;
        i++;
        while (total % 10 == 0)
        {
            cnt++;
            total = total / 10;
        }
        if (total >= 100000)
        {
            tmp = total / 100000;
            tmp = tmp * 100000;
            total = total - tmp;
        }
    }
 
    printf("%d", cnt);
 
 
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>