[APS][C++] BOJ S5 1676번 팩토리얼 0의 개수 (feat. 0의 개수의 비밀)

https://www.acmicpc.net/problem/1676

---

문제

$ N! $ 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

• 첫째 줄에 구한 0의 개수를 출력한다.

---

풀이

$ N! $ 에서 0의 개수는 5의 지수(소인수로서 5가 총 몇번 곱해졌는지)를 확인하면 된다.

• 연속된 0의 개수는 팩토리얼의 소인수 분해에서 10이 몇 번 곱해졌는지에 따라 변화함
• 10은 2와 5가 각각 하나씩 모일 때마다 만들어지기 떄문에 소인수로서 5가 총 몇 개가 있느냐에 따라 결정됨 (2는 모든 짝수의 소인수이기 때문에  소인수로서 2는 5보다 무조건 많을 수 밖에 없음)
• 아래 수식을 코드로 구현하면 해결이 가능함

$$ \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + \cdots $$

---

코드

#include <cmath>
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;

  int cnt = 0;
  for (int i = 1; i < 4; i++) {
    cnt += N / int(pow(5, i));
  }

  cout << cnt;

  return 0;
}

---

결과

---

오답 원인

• 처음에는 위 규칙이 아니라 팩토리얼을 모두 계산한 후 0을 세는 방식으로 작성했더니 C++에서 표현할 수 있는 수의 범위를 넘어갔기 떄문에 오답이 출력됨 (오버플로우로 인한 오류)
• 따라서 오버플로우를 방지하기 위해 다른 방법이 필요하였으며, 위 코드를 통해 해결