[C++][백준 1676] 팩토리얼 0의 개수

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

 

제출 코드(오답)

#include <iostream>
#include <string>
using namespace std;

int getFactorial(int a)
{
    long long res = 1;
    for (int i = 1; i <= a; i++)
        res = res * i;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, count = 0;
    cin >> n;
    string str = to_string(getFactorial(n));
    for (int i = str.length() - 1; i >= 0; i --)
    {
        if (str[i] != '0') break;
        count++;
    }
    cout << count;
}

가장 처음에 작성했던 코드인데, 문제될 게 없어보이는데 틀렸다고 떠서 최대값인 500!를 검색해보았는데

500! = 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

숫자 형태로 담을 수 없을 듯한 수가 등장했다(참고로 n = 500일때 정답은 124이다)

원래 하려던 방법인 팩토리얼 값을 구한 뒤 문자열로 바꿔 0의 개수를 계산하는 것 대신 다른 방법으로 접근해야겠다고 생각했다

 

결국 뒤에 나오는 0의 개수를 알고 싶은 거고, 뒤쪽에 0이 나온다는 것은 계산 과정에서 10이 곱해졌다는 의미다

따라서 500 * 499 * 488 * ... * 1의 과정 속에서 10이 얼마나 곱해졌는지를 구해주면 된다

10은 2와 5로 소인수분해되므로 팩토리얼을 계산하기 위해 곱해지는 각 수에서 2와 5가 몇 번 등장하는지를 계산하면 되겠다고 생각이 들었다

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    int count[2] = {};
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int num = i;
        while(1)
        {
            if (num % 2 == 0)
            {
                num /= 2;
                count[0]++;
            }
            else if (num % 5 == 0)
            {
                num /= 5;
                count[1]++;
            }
            else
                break;
        }
    }
    cout << min(count[0], count[1]);
}

이런 식으로 곱해지는 각 i에서 2와 5의 등장 횟수를 세어 준 뒤, 10만큼이 곱해진 횟수를 찾아야 하기 때문에 둘 중 더 최소로 등장한 값을 출력해 주었다