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

● [문제번호 1676] 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

● 알아야 할 것

: 소인수분해

 

● 풀이 과정

: 팩토리얼을 구하고 결과값의 끝자리부터 하나씩 0의 갯수를 세면 '시간 초과' 결과가 나온다.

 

: 팩토리얼을 구하는 다른 방법을 생각해봤지만 다른 방법이 떠오르지 않자 문제에서 힌트를 찾으려고 하였다.

다른 숫자도 아닌 0이 끝에서부터 연속된 갯수를 찾는 문제라는 것은

10이 몇 개 곱하여 졌는가 → 소인수분해를 했을 때 2의 지수와 5의 지수를 구하여라

와 같은 문제로 이해할 수 있다.

 

: 하지만 소인수분해의 과정을 코드로 표현하기 어려워서 구글링을 하였다.

 

: 예를 들어 100! 의 끝자리 0의 갯수를 구한다고 한다면

 

소인수분해를 통해 2의 지수

= (100/2) + (100/(2*2)) + (100/(2*2*2)) + (100/(2*2*2*2)) + (100/(2*2*2*2*2)) + (100/(2*2*2*2*2*2))

= 50 + 25 + 12 + 6 + 3 + 1

= 97

 

소인수분해를 통해 5의 지수

= (100/5) + (100/(5*5))

= 20 + 4

= 24

 

이므로 이 중 작은 값만큼 끝자리 0의 갯수가 생기게 된다

 

● 주의 할 것

: 주어진 수에 2 또는 5가 몇 개인지 구할 때

주어진 수 보다 작은 제곱수가 될 때 까지 반복해야한다

 

● 참고 할 것

: 문제 풀이 방법을 떠올리기 위한 링크

https://ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int N, cnt;

// 숫자의 뒷자리 0은 2와 5의 곱을 통해 나온다
// 주어진 수에 2가 몇개 들어있는 지
// 주어진 수에 5가 몇개 들어있는 지
// 확인하여 작은 갯수를 출력하면 된다
void count_zero()
{
    // 2가 몇개 들어있는 지
    // 5가 몇개 들어있는 지
    int two_cnt = 0;
    int five_cnt = 0;
    // 주어진 수보다 작은 제곱수가 될 때 까지 커진다
    int two = 2;
    int five = 5;
    
    // 예를 들어
    // 100까지의 모든 수 중에 2가 들어있는 갯수는
    // (100/2) + (100/(2*2)) + (100/(2*2*2)) + (100/(2*2*2*2)) + ...
    while(two <= N)
    {
        two_cnt += N / two;
        two *= 2;
    }
    
    // 위의 예시와 동일 작업
    while(five <= N)
    {
        five_cnt += N / five;
        five *= 5;
    }
    
    // 2의 지수와 5의 지수 중에 작은 수만큼 0이 생긴다
    cnt = min(two_cnt, five_cnt);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    count_zero();
    
    cout << cnt;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [300 - 수학 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10430	나머지	https://pirateturtle.tistory.com/180
2	2609	최대공약수와 최소공배수	https://pirateturtle.tistory.com/181
3	1934	최소공배수	https://pirateturtle.tistory.com/182
4	1978	소수 찾기	https://pirateturtle.tistory.com/183
5	1929	소수 구하기	https://pirateturtle.tistory.com/184
6	6588	골드바흐의 추측	https://pirateturtle.tistory.com/185
7	10872	팩토리얼	https://pirateturtle.tistory.com/186
8	1676	팩토리얼 0의 개수	https://pirateturtle.tistory.com/187
9	2004	조합 0의 개수	https://pirateturtle.tistory.com/188