[백준 9916] Zeros (C#, C++) - soo:bak

문제 링크

9916번 - Zeros

설명

자연수 n이 주어질 때 n!을 십진수로 썼을 때 나타나는 0의 총 개수를 구하는 문제입니다.

접근법

n이 100 미만이므로 팩토리얼을 직접 계산할 수 있습니다.

큰 수 연산을 위해 배열에 각 자릿수를 저장하고 곱셈을 수행합니다.

계산이 끝나면 결과에서 0의 개수를 세어 출력합니다.

---

Code

C#

using System;
using System.Numerics;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var fact = BigInteger.One;
    for (var i = 2; i <= n; i++)
      fact *= i;

    var cnt = 0;
    foreach (var c in fact.ToString()) {
      if (c == '0')
        cnt++;
    }

    Console.WriteLine(cnt);
  }
}

C++

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

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  vi digits(200, 0);
  digits[0] = 1;
  int len = 1;

  for (int i = 2; i <= n; i++) {
    int carry = 0;
    for (int j = 0; j < len; j++) {
      int prod = digits[j] * i + carry;
      digits[j] = prod % 10;
      carry = prod / 10;
    }
    while (carry > 0) {
      digits[len++] = carry % 10;
      carry /= 10;
    }
  }

  int cnt = 0;
  for (int j = 0; j < len; j++) {
    if (digits[j] == 0)
      cnt++;
  }

  cout << cnt << "\n";

  return 0;
}