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

Kim Yuhyeon·2022년 4월 26일

cpp 백준 알고리즘

알고리즘 + 자료구조

목록 보기

44/161

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

문제

알고리즘 접근 방법

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제이다.

방법 1

뒤에서부터 0의 개수를 센 뒤 +1 해서 출력
그러나 N의 최대값이 500이기 때문에
N!을 직접 구하는 건 무리,,

500! =
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496
4475022032818630136164771482035841633787220781772004807852051593292854779075719393306037
7296085908627042917454788242491272634430567017327076946106280231045264421887878946575477
7149863494367781037644274033827365397471386477878495438489595537537990423241061271326984
3277457155463099772027810145610811883737095310163563244329870295638966289116589747695720
8792692887128178007026517450776841071962439039432253642260523494585012991857150124870696
1568141625359056693423813008856249246891564126775654481886506593847951775360894005745238
9403357984763639449053130623237490664450488246650759467358620746379251842004593696929810
2226397195259719094521782333175693458150855233282076282002340262690789834245171200620771
4640979456116127629145951237229913340169552363850942885592018727433795173014586357570828
3557801587354327688886801203998823847021514676054454076635359841744304801289383138968816
3948746965881750450692636533817505547812864000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000

한눈에 봐도 무리임. . !!!

방법 2

뒤에 0이 나오는 경우 = 10이 곱해진 경우
10 = 2 * 5 이므로,
N! 을 소인수분해 했을 때 나오는 2와 5의 개수를 세서 더 적은 것을 구하면 된다.
기본적으로 2가 훨씬 많으므로,
5의 개수만 세서 0이 몇개 나오는 지 알 수 있다.
주의할 점은 5의 제곱수가 나올 때이다.
25 -> 5가 2번 곱해진 것이므로 0을 2개 만들 수 있다.
125 -> 5가 3번 곱해진 것이므로 0을 3개 만들 수 있다.
따라서 주어진 n을 5로 나눈 몫 + 25로 나눈 몫 + 125로 나눈 몫을 더하면 답을 구할 수 있다!

풀이

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int ans = 0;

    int N;
    cin >> N;

    for (int i=5; i<=N; i*=5)
        ans += N/i;
    cout << ans << '\n';
  
    return 0;
}