cpp) 백준 1676: 팩토리얼 0의 개수

Problem

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

1676번: 팩토리얼 0의 개수

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

 

 

Solution

#include<iostream>
#include<string>

using namespace std;

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

    int n;
    cin >> n;

    int cnt = 0;  // 0의 개수
    for (int i=5;i<=n;i*=5){
        cnt += n/i;
    }

    cout << cnt << '\n';
    
   return 0;
}

 

N이 500이하의 수이기 때문에 팩토리얼 재귀 문제로 풀면 시간 초과가 날 수밖에 없다. 뒤에 0이 나오는 경우는 10이 곱해진 경우밖에 없다. 10은 2와 5로 나타낼 수 있기 때문에 N! 을 소인수분해 했을 때 나오는 2와 5의 개수를 세서 min(2의 개수, 5의 개수)를 구하면 된다. 하지만 이러한 과정 없이, 2의 개수보다 5의 개수가 항상 적기 때문에 5의 개수만 세도 된다. 100! 의 0의 개수를 계산한다고 가정했을 때, 인수가 5로 들어가는 것을 발견하면 +1, 인수가 5*5인 것은 +2, 이런 식으로 더하면 5의 개수를 셀 수 있다. 

 

 

Reference

https://torbjorn.tistory.com/247

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