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

문제출처: https://www.acmicpc.net/problem/1676

풀이

도대체 어떻게 풀 수 있는 문제일까 고민을 많이 했는데 딱히 떠오르지 않아서 구글링을 통해 10은 2*5으로 이루어진다는 힌트만 얻고 대충 1!부터 10!부터 노트에 적어보며 규칙성을 찾아보았습니다. (사실 위의 힌트가 정답의 전부입니다.)

1!= 1*1

2!= 2*1

3!= 3*2*1

4!= 4*3*2*1

5!= 5*4*3*2*1

6!= 6*5*4*3*2*1

7!= 7*6*5*4*3*2*1

8!= 8*7*6*5*4*3*2*1

9!= 9*8*7*6*5*4*3*2*1

10!= 10* 9*8*7*6*5*4*3*2*1

이렇게 펼쳐본다음 위에서 얻은 힌트를 이용해서 팩토리얼을 구성하는 숫자들을 2와 5로 쪼개어 보았습니다. 그리고 쪼갠 숫자들을 나열하여 2와 5가 각각 몇번 나오는 지를 세어보았습니다.

2!= 2*1 => 2: 1개, 5: 0개

3!= 3*2*1 => 2: 1개, 5: 0개

4!= 2*2*3*2*1 => 2: 3개, 5: 0개

5!= 5*2*2*3*2*1 => 2: 3개, 5: 1개

6!= 2*3*5*2*2*3*2*1 => 2: 4개, 5: 1개

7!= 7*2*3*5*2*2*3*2*1 => 2: 4개, 5: 1개

8!= 2*2*2*7*2*3*5*2*2*3*2*1 => 2: 7개, 5: 1개

9!= 9*2*2*2*7*2*3*5*2*2*3*2*1 => 2: 7개, 5: 1개

10!= 2*5*9*2*2*2*7*2*3*5*2*2*3*2*1 => 2: 8개, 5: 2개

1!~ 10! 까지 계산된 수를 모두 구해서 정답을 구해보면 위의 규칙성 중 팩토리얼 숫자 중 2로 구성된 수의 갯수와 5로 구성된 수의 갯수 중 더 적은 갯수와 일치함을 알 수 있습니다.

알고리즘을 알았으니 반복문을 통해 식을 작성할 텐데 각 팩토리얼 수의 2와 5의 갯수를 구하는 식은 아래 소스코드에 나와있습니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    int n;
    int two = 0, five = 0;
    cin >> n;
    
    for (int i = 2; i <= n; i = i * 2)
    
        two += n / i;
    for (int i = 5; i <= n; i = i * 5)
        five += n / i;
 
    cout << min(two, five);
    
    return 0;
}

결과