(매일 BOJ) C++ 1676번 팩토리얼 0의 개수

이번 문제는 실버 5 난이도의 1676번 팩토리얼 0의 개수 문제이다.

 

처음 작성한 코드이다.

 

접근법

팩토리얼을 직접 브루트포스로 계산한 후 이를 to_string 함수를 사용하여 string으로 바꾸고 뒤에서부터 '0'를 count 하는 방식으로 구현하였다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    int mutiply = 1;
    for (int i = 1; i < N+1; i++){
        mutiply *= i;
    }
    string str;
    str = to_string(mutiply);
    int zero_count = 0, i = str.size() -1;

    while (1){
        if (str[i] == '0') {
            zero_count += 1;
            i -= 1;
        }
        else break;
    }
    cout << zero_count;
}

1차 코드 실패 이유

그냥 브루트포스를 사용하여 곱으로 팩토리얼을 만든 후 0을 count 하면 13! 에서 int 오버플로우 / 20! 에서 long long 오버플로우가 된다.

수학적 알고리즘

10이 만들어지려면 2와 5의 쌍이 존재하여야 한다.
하지만 2보다 5의 개수가 더 적기 때문에 5의 개수를 count 하면 0의 개수를 수학적으로 알아낼 수 있다.

N!의 끝자리 0의 개수 = N / 5 + N / 25 + N / 125 + ...

 

2차 코드

/* 
그냥 브루트포스를 사용하여 곱으로 팩토리얼을 만든 후 0을 count 하면 13! 에서 int 오버플로우 / 20! 에서 long long 오버플로우가 된다.
따라서 다른 방법을 찾아야 함
10이 만들어지려면 2와 5의 쌍이 존재하여야 한다.
하지만 2보다 5의 개수가 더 적기 때문에 5의 개수를 count 하면 0의 개수를 수학적으로 알아낼 수 있다.
 */

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N, zero_count = 0;
    cin >> N;
    
    for (int i = 5; i <= N; i *= 5){
        zero_count += N / i;
    }
    
    cout << zero_count;
}