백준 1676: 팩토리얼 0의 개수/수학식찾기

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

처음에 팩토리얼 구하고 뭐 하고 막 했는데 그럴필요 전혀 없는 문제였다..

마지막에 0이 나오려면, 2*5가 들어있어야 하는데, 이때 5가 2의 개수보다 적으므로 N!에서의 5의 개수를 구해주면 된다.

나는 1부터 N까지 각각 5로 나누어 떨어지면 그걸 일일이 구했는데, 정석으로 풀면, N에서 5의 x승으로 나눈 몫을 각각 더해주면 그것이 총 5의 개수, 즉 0의 개수가 된다.

내 코드:

#include <iostream>
#include <string>
#include <cmath>
using namespace std;


int main() {
    int N;
    cin >> N;
    int cnt = 0;
    int tmp;
    for (int i = 1; i <= N; i++) {
        tmp = i;
        while (tmp % 5 == 0) {
            cnt++;
            tmp /= 5;
        }
    }
    
    cout << cnt;
    return 0;
}

정석 코드:

#include <iostream>
#include <string>
#include <cmath>
using namespace std;


int main() {
    int N;
    cin >> N;
    int cnt = 0;
    int tmp;
    for (int i = 5; i <= N; i*=5) {
        cnt += N / i;
    }
    
    cout << cnt;
    return 0;
}

​