[백준 7489] 팩토리얼 (C#, C++) - soo:bak

문제 링크

7489번 - 팩토리얼

설명

팩토리얼을 전부 계산하지 않고 n!의 최우측 0이 아닌 숫자를 찾는 문제입니다.

접근법

먼저 1부터 n까지 곱하면서 뒤의 0을 제거합니다. 예를 들어 5!을 계산할 때 120이 되면 뒤의 0을 제거해 12로 만듭니다. 최우측 0이 아닌 숫자를 찾기 위해 뒤의 0은 필요 없기 때문입니다.

다음으로 값이 너무 커지는 것을 막기 위해 일정 자릿수만 남기고 진행합니다. 최우측 0이 아닌 숫자에 영향을 주지 않는 범위에서만 자릿수를 제한하면 되므로, 충분한 자릿수를 유지하면서 계산을 진행할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    for (var tc = 0; tc < t; tc++) {
      var n = int.Parse(Console.ReadLine()!);
      var res = 1;

      for (var i = 2; i <= n; i++) {
        res *= i;
        while (res % 10 == 0) res /= 10;
        res %= 1000000;
      }

      Console.WriteLine(res % 10);
    }
  }
}

C++

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

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

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    int res = 1;

    for (int i = 2; i <= n; i++) {
      res *= i;
      while (res % 10 == 0) res /= 10;
      res %= 1000000;
    }

    cout << res % 10 << "\n";
  }

  return 0;
}