[BOJ] 1676번 팩토리얼 0의 개수

복기

-

코드

• C++ 17

#include <iostream>   using namespace std;   int N; int Memo[501] = { 0, 0, 0, 0, 0, 1 };   int CountZero(int n) {     if (Memo[n] || n <= 5)         return Memo[n];          // 0의 개수를 구한다는 것은 그 수를 인수분해 했을 때,     // 10의 지수가 몇이냐는 말과 같다.     // 10을 인수분해하면 2 * 5가 되는데,     // 2의 지수는 항상 5의 지수보다 많으므로     // 결과적으로는 5의 지수만 구하면 된다.       // N!에서의 5의 개수는     // N에 대해서 5가 몇 번 나오는지,     // 그리고 그 몫에 대해서도 5가 몇 번 나오는지 계산하면 된다.     // 따라서 이를 점화식으로 나타내면     // C(N) = (N / 5) + C(N / 5)가 된다.     // C(n)은 n!에 대해 0의 개수를 구하는 함수다.     Memo[n] = (n / 5) + CountZero(n / 5);       return Memo[n]; }   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> N;     cout << CountZero(N); }

• C# 6.0

using System;   namespace Algorithm {     class Program     {         static int N;         static int[] Memo = new int[501];           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             Console.Write(CountZero(N));         }           static int CountZero(int n)         {             if (Memo[n] != 0 || n < 5)                 return Memo[n];                          Memo[n] = (n / 5) + CountZero(n / 5);               return Memo[n];         }     } }

• Python 3

from sys import stdin, setrecursionlimit input = stdin.readline setrecursionlimit(1000000)   N = int(input()) Memo = [0] * 501   def CountZero(n):     if Memo[n] or n < 5:         return Memo[n]          Memo[n] = (n // 5) + CountZero(n // 5)     return Memo[n]   print(CountZero(N))