[BOJ-1676][C++] 팩토리얼 0의 개수

문제

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

 

입력

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

 

출력

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

 

예제 입력 1 

10

 

예제 출력 1

2

 

예제 입력 2 

3

 

예제 출력 2

0

 

알고리즘 분류

• 수학
• 임의 정밀도 / 큰 수 연산

 

문제 출처

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

1676번: 팩토리얼 0의 개수

 

---

 

문제 해결 방법

• 특정 숫자의 팩토리얼을 구했을 경우, 맨뒤에 연속으로 나오는 0의 개수를 출력시키는 문제이다.
• 어떤 숫자의 뒷자리 숫자가 0이 되려면, 그 숫자는 2와 5의 곱으로 이루어져 있어야 한다.
  • 10 : 2 x 5
  • 100 : 2² x 5²
  • 1000 : 2³ x 5³
  • 130 : 2 x 5 x 13
  • ...
• 다음과 같이 규칙을 확인해보면 N을 5로 나눈 몫의 값을 출력시켜주면 된다는 것을 확인할 수 있다.
  • 단, N = 25일 경우, 0의 개수는 25 / 5 = 5가 아닌 6이다. 그 이유는 뒷 자리에 0이 n개 있다는 것은 2와 5가 n개씩 짝지어져 있다는 것을 의미하고, 25!의 경우에는 2가 22개, 5개 6개로, 2와 5가 6개로 짝지어져 있기 때문이다.

이미지 출처 : https://st-lab.tistory.com/165

while (N >= 5) {
    count += N / 5;
    N /= 5;
}

• 또는 다음과 같은 알고리즘을 사용할 수 있다.

for (int i = 5; i <= N; i *= 5) {
    count += (N / i);
}

• 이곳에 이 문제에 대한 설명이 자세히 소개되어 있다.

 

코드

#include <iostream>
using namespace std;

int N, count;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    while (N >= 5) {
        count += N / 5;
        N /= 5;
    }

    cout << count << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 실버V