Baekjoon 1676번 팩토리얼 0의 개수

문제

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

걸린 시간

00 : 53 : 56 실패

풀이

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i < n+1; i++){
        if(i%5 == 0) ans++;
        if(i%25 == 0) ans++;
        if(i%125 == 0) ans++;
    }
    cout << ans << "\n";
    return 0;
}

0의 개수가 증가하는 규칙을 찾지 못해 결국 풀이를 보게 된 문제.

2와 5의 곱인 10의 개수에 따라서 0의 개수가 결정된다. 2의 배수는 5의 배수보다 항상 많거나 같으므로 5의 배수만 생각하면 된다. 이 때 5의 제곱수를 꼭 고려해야한다.

스스로 문제를 풀 때 팩토리얼 수를 쭉 나열해 보고 5의 배수마다 0의 개수가 하나씩 증가한다는 규칙을 찾았지만 수학적으로 왜 그런지를 생각해보려 하지 않아서 틀린 것 같다.

참고로 이 문제를 동적 계획법으로도 접근한 풀이가 있어 아래에 첨부했다.

참고

• 팩토리얼의 끝 0의 개수 구하기 - Parkito's on the way