[백준 1975] Number Game (C#, C++) - soo:bak

문제 링크

1975번 - Number Game

설명

정수 N을 여러 진법으로 나타냈을 때, 각 진법에서의 연속된 0의 개수를 모두 더해 출력하는 문제입니다.

접근법

N을 b진법으로 나타낼 때 끝자리 0의 개수는 b가 N을 나누는 횟수와 같습니다.

b가 N보다 크면 끝자리 0은 생기지 않으므로 b는 2부터 N까지만 확인하면 됩니다.

N의 범위가 작으니 1부터 1000까지의 답을 미리 계산해두고 테스트 케이스마다 출력합니다.

---

Code

C#

using System;
using System.IO;
using System.Text;

class Program {
  static void Main() {
    var ans = new int[1001];
    for (var n = 1; n <= 1000; n++) {
      var total = 0;
      for (var b = 2; b <= n; b++) {
        var x = n;
        while (x % b == 0) {
          total++;
          x /= b;
        }
      }
      ans[n] = total;
    }

    using (var sr = new StreamReader(Console.OpenStandardInput())) {
      var sb = new StringBuilder();
      var t = int.Parse(sr.ReadLine()!);
      for (var i = 0; i < t; i++) {
        var n = int.Parse(sr.ReadLine()!);
        sb.AppendLine(ans[n].ToString());
      }
      Console.Write(sb);
    }
  }
}

C++

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

typedef vector<int> vi;

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

  vi ans(1001, 0);
  for (int n = 1; n <= 1000; n++) {
    int total = 0;
    for (int b = 2; b <= n; b++) {
      int x = n;
      while (x % b == 0) {
        total++;
        x /= b;
      }
    }
    ans[n] = total;
  }

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    cout << ans[n] << "\n";
  }

  return 0;
}