[C++] N!에서 0의 개수

[문제]

자연수 N을 입력받으면 N! 값에서 연속적으로 '0'이 몇 개 있는지 구하는 프로그램을 작성하시오.

 

[입력예제]

12

 

[출력예제]

2

 

12!은 '479001600'으로 연속적으로 0이 2번 사용되었기에 2를 출력하였다.

---

[코드]

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, num, div, two, five, res;
    
    //1
    cin >> n;
    
    //2
    for(int i=2; i<=n; i++){
        //3
        num = i;
        div = 2;
        //4
        while(1){
            if(num%div==0){
                if(div==2) two++;
                else if(div==5) five++;
                num/=div;
            }
            //5
            else div++;
            //6
            if(num==1) break;
        }
    }
    
    //7
    res = two < five ? two : five;
    
    //8
    cout << res;

    return 0;
}

 

[설명]

처음엔 N!을 구해서 0의 개수를 구하려 했지만 입력받는 N이 커지게 되면 int형의 범위를 벗어나게 되어 값을 구할 수가 없다.

이 게시글 바로 전에 했던 'N!의 표현법'에 나오는 소인수 분해를 이용하여 구하는 방법을 사용하였다.

0이 나오는 경우는 10이 몇개인지 찾으면 되는데, 10은 소인수 분해를 하였을 시 2 × 5로 이루어져 있으므로, N까지의 숫자에서 '2'와 '5'를 가지고 있는 숫자들을 찾아 개수를 세어 준 뒤, '2'와 '5'의 짝이 맞아야 하니 더 작은 개수를 가진 변수를 출력해 주면 된다.

 

1. N을 입력받는다.
2. 1은 곱해도 1이니 2부터 N까지의 반복문(3~6)을 실행한다.
3. 현재 숫자 i는 num변수에 넣어주고 나눠지는 숫자 div는 2를 넣어준다.
4. while문(4~6)을 돌며 만약 num과 div가 나누어 떨어지는 경우 이때 div가 2면 two변수를 1 증감시키고, div가 5면 five변수를 1 증감시켜준 후, num변수엔 div와 나눈 몫을 넣어준다.
5. num과 div가 나누어 떨어지지 않는 경우 div값을 1증가시켜준다.
6. 만약 num값이 1이 되면 while문을 빠져나온다.
7. 삼항연산자를 이용하여 res변수에 더 작은 숫자를 가진 변수 값을 넣어준다.
8. res를 출력한다.

 

[실행결과]