[백준] 3474번 교수가 된 현우 C++ 코드

코드

#include <bits/stdc++.h>

using namespace std;
int t,n;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> t;
  while(t--) {
    cin >> n;
    int cnt = 0;
    int five = 5;
    while (five <= n) {
      cnt += (int)n/five;
      five *= 5;
    }
    cout << cnt << "\n";
  }
  return 0;
}

데이터 최대 크기가 10억이라서 O(logN) 이하의 시간 복잡도를 구상해야했다. 처음에 모듈러 연산을 떠올렸다가 도저히 그림이 안나와서 다른 방식을 생각했다. 0의 개수 세기기 때문에 5또는 10과 관련이 있을 것이라 생각했고 규칙을 찾아냈다. 주어진 수보다 작거나 같은 5의 제곱수의 배수 개수를 찾아주면 된다. 입출력이 많기 때문에 빠른 입출력을 사용하였다.