백준 1436번-팩토리얼 0의 개수 문제 C++

📍백준 1436번-팩토리얼 0의 개수 문제 C++

 

---

🧩 문제 요약 

정수 N이 입력될 떄 N!의 뒤에 있는 0의 개수를 구하는 것 . 

---

👍 이 문제에서 배운점 

이 문제를 처음에 보면 factorial을 돌려서 %10해서 갯수를 카운팅 하면 되지 않을까? 라고 모두가 생각한다. 

하지만, 이렇게 풀면 당연히 시간초과에 걸리게 된다.

 

그럼 어떻게 문제에 접근해야 할까? 

0이 언제 생기게 되는지를 생각하면된다. 

 

✅ 0은 언제 생기는가? 

팩토리얼 결과에 0이 생기는 이유는 10이 곱해지기 때문이다.

👉 10=2*5니까, 팩토리얼에서 2와 5가 몇개 있는지를 따져야한다.

 

그런데, 여기서 주의할점은!!

2가 5보다 훨씬 많이 등장한다는 것이다. 

2는 짝수이기만 하면 등장한다. 

그렇기 때문에 우리는 5의 개수에 집중하면 된다. 

 

여기서 생기는 의문은 그러면 5의 배수를 구하면 되는 건가? 하는 생각이 든다. 

하지만 우리는 5의 제곱을 구해야한다. 

 

✅ 5의 제곱

앞서 말했듯이 0이 발생하는 이유는 10이 곱해지기 때문이다. 

우리는 이것을 구하기 위해 2*5에서 5의 개수를 구하면 된다고 했다. 

단순히 5의 배수만 세면 안되는 이유는 다음과 같다. 

 

예를 들어 N이 25라고 할때, 

 

1부터 25까지 숫자중 5의 배수는 5, 10, 15, 20, 25이다. 

그래서 단순히 생각하면 25/5 ==> 5라고 생각할 수 있다. 

 

👉하지만< 25는 5*5로 5가 2번 들어간다. 

 

5의 개수를 구해야하는데 5로만 나누면 25, 50과 같이 5가 2번 들어가는 숫자들을 놓치게 된다. 그래서 5, 25, 125와 같이 5의 배수를 사용하면 정확한 5의 개수를 알 수 있다. 

 

이를 일반화 하면 

• N/5 : 5가 한번 들어간 수 
• N/25 : 5가 두번 들어간 수 
• N/125 : 5가 세번 들어간 수 

가 된다. 

---

🧾 내가 구현한 코드 

#include <iostream>
#include <string> 
using namespace std; 

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

    int n, cnt= 0 ; 
    cin >> n; 

    for(int i = 1; i<n+1 ;i++){
        if(i%125 == 0) cnt +=3;
        else if(i%25==0) cnt+=2;
        else if(i%5==0) cnt++;
    }
    cout << cnt << "\n";
}

 

원래 내가 구현한 코드는 for문으로 i를 1~N까지 돌며 5의 제곱의 배수들을 일일이 카운팅 했다. 

 

하지만, 아래의 백준 상위 코드 처럼 입력으로 받은 N을 5의 제곱으로 나눠주면 몫을 통해 5의 개수를 바로 구할 수 있다.

---

🧾백준 상위 코드 

#import<ios>
main(int i){scanf("%d",&i);printf("%d",i/5+i/25+i/125);}

이 코드는 아주 간단히 계산할 수 있어 시간복잡도가 (O(logN))로 매우 빠르다. 

 

이렇게 계산 할 수 있는 이유는 

예를 들어 N이 100이라고 할 때, 

1~100까지 중에서 5로 나눠지는 수는 100/5로 20개가 있다. 

 

또한 1~100까지 중에서 25로 나눠지는 수는 100/25로 4가지가 있다. 

 

그럼 이때, 25랑 75는 겹치지 않나? 라고 생각할 수 있다. 

 

하지만 N / 5에서 이미 한 번 센 거니까  N/25로 한 번 더 세주면 정확히 총 2번 들어간 게 된다. 

 

 

이렇게 생각하면 간단하게 한줄로도 구현이 가능하다. 

---