0의 개수가 n개인 팩토리얼 수 찾기

코드포스 문제가 매우 재미있는 문제여서 문제와 함께 풀이를 적으려 한다.

사실 풀이라기 보다는 이러한 알고리즘 생각 방식에 대해 알아놓으면 좋은 것 같다.

문제 출처 :

http://codeforces.com/contest/633/problem/B

문제는 다음과 같다.

수 n이 주어졌을 때, 팩토리얼 끝자리의 0의 개수가 n개인 모든 값을 찾으시오.

예를 들면 n = 1인경우

5! = 120, 6! = 720, 7! = 5040, 8! = 40320 그리고 9! = 362880

위의 5개의 수만이 뒷자리 0이 1개이기 때문에 총 답은 5개이다.

이러한 알고리즘에 대해 생각해보자.

우리는 어떤 수 x!의 끝자리 0의 개수가 몇개인지 알아야 한다.

사실상 생각해보면 결국 어떤수의 팩토리얼에서 뒷자리가 0이 될 수 있는 조건은 5와 2가 곱해졌을때이다.

20을 보자. 5*2*2이고, 5와 2가 쌍으로 1개씩 있었으므로 20이 된다.

5와 2가 쌍으로 3개가 있다면 5*2*5*2*5*2 = 1000이다. 즉 0이 3개가 된다.

따라서 이 방식을 생각하여 우리는 알고리즘을 구상해본다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int five, two;
vector<int> ans;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; min(five, two) <= n; i++)
    {
        int j = i;
        while (j % 5 == 0)
        {
            j /= 5;
            five++;
        }
        j = i;
        while (j % 2 == 0)
        {
            j /= 2;
            two++;
        }
 
        if (min(five, two) == n)
            ans.push_back(i);
    }
 
    cout << ans.size() << endl;
 
    for (auto i : ans)
        cout << i << " ";
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 코드를 보면 다음과 같다.

1부터 시작하여 min(five, two) <= n일때 까지 i ++를 한다.

이때 i는 1*2*3*4*5*6*7*8*9*...*i*.. 라고 생각 할 수 있다.

그리고 이때 min(five, two)의 의미는 5와 2가 짝을 이루는 개수를 의미한다.(0이 총 몇개가 생길지 의미한다.)

첫번째 while문에 의해 5의 개수를 구할 수 있고

두번째 while문에 의해 2의 개수를 구할 수 있다.

이렇게 하여 5와 2의 짝의 개수가 n개랑 같다면 그것을 ans 벡터에 푸쉬해줌으로써 우리는 이 문제를 해결 할 수 있게된다.

이렇게 생각해보면 매우 간단한 문제이지만, 과연 아무것도 없는 상황에서 PS로 주어진다면 쉽게 해결 할 수 있을지 궁금하다.

팩토리얼에서 0의 개수를 구할때는 5와 2가 핵심이 된다는 것을 명확하게 알려주는 코드임을 알 수 있다.