백준_1676 : 팩토리얼 0의 개수 - C++

문제

---

문제 해석

- 입력 받은 수의 팩토리얼가 뒤에 0이 몇개 붙는지를 세면 되는 문제이다.

---

알고리즘

- 곱에서 뒷자리가 0이 나오는 경우는 2의 배수와 5의 배수가 곱해지는 경우이다.

- 팩토리얼은 1부터 순서대로 곱하기 때문에 5의 배수가 곱해 질 때는 항상 짝수와 곱해진다.

- 이때 주의 할 점은 25, 125 처럼 5의 제곱수가 곱해질 때는 5가 2번 3번 곱해질 때는 0 또한 2개, 3개가 붙는다.

- 정리하면 숫자 N 이 주어 졌을 때 1 ~ N 까지 하나씩 증가 시키며 

  - 5의 배수가 나올 때 마다 0이 하나씩

  - 25의 배수가 나올 때 마다 0이 두개씩

  - 125의 배수가 나올 때 마가 0이 세개씩 붙게 된다.

- 이를 모두 count 해 주면 뒤에 붙는 0의 총 개수가 나오게 된다.

---

코드

 

#include <iostream>
using namespace std;

int input;

int main(){
    cin >> input;
    int cnt = 0;
    for(int i = 1; i <= input; i++){
        if(i % 5 == 0){
            cnt += 1;
        }
        if(i % 25 == 0){
            cnt += 1;
        }
        if(i % 125 == 0){
            cnt += 1;
        }
    }
    cout << cnt << '\n';
}