[백준] 1676.cpp : 팩토리얼 0의 개수

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

#include <iostream>
using namespace std;

int main(void)
{
  int n;
  cin >> n;
  int num2 = 0, num5 = 0;
  int tar;
  // 1 ~ n 까지 인수분해하여 2의 갯수와 5의 갯수 세어줌
  for(int i = 1 ; i <= n ; i++)
  {
    tar = i;
    // 2의 갯수
    while(tar % 2 == 0)
    {
      num2++;
      tar /= 2;
    }
    // 5의 갯수
    while(tar % 5 == 0)
    {
      num5++;
      tar /= 5;
    }
  }
  // 더 작은 값 출력
  num2 >= num5 ? cout << num5 << '\n' : cout << num2 << '\n';
}

 

[Approach]

1. N 이하의 수들에 대해서 2와 5의 갯수들을 세어주려고 했는데, 전부 곱하면서 10으로 계속 나눠주는게 더 편할 것 같다.

     -> 시간초과가 난다.

2. 처음에 생각했던 대로 2와 5의 갯수들을 세는 걸로 하자

 

[Point]

1. 곱하는건 왜 시간초과이고, 모든 애들을 인수분해하는 건 왜 시간초과가 안 나는 것일까?

     -> 아마 10으로 나누기만 하면 안 나눠떨어지는 부분이 기하급수적으로 커져서 연산을 못하거나, 오버플로우가 나서 그런 것 같다.

2. 굳이 2의 갯수까지 카운트해줄 필요는 없을 것 같다. 1~5 까지만 하더라도 5의 갯수가 적기에, 무조건적으로 5의 갯수가 적다.

 

[More]

1.  n/5 + n/25 + n/125 가 성립하는 이유 역시 5의 갯수를 세어주는 일인데, 25와 125 같은 경우는 5가 두번씩 들어가기 때문에 5에 

     서 한번, 25 를 통해 한번 더 (총 2번), 125를 통해 한번 더 (총 3번) 세는 방식이다.