N!에서 0의 개수

▣ 문제

- 자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그 램을 작성하세요. 만약 5! = 5 ×4 × 3 × 2 ×1 = 120으로 일의자리부터 연속적된 ‘0’의 개수는 1입니다. 만약 12! = 479001600으로 일의자리부터 연속적된 ‘0’의 개수는 2입니다.

 

▣ 입력설명

- 첫 줄에 자연수 N(10<=N<=1,000)이 입력된다.

 

▣ 출력설명

- 일의 자리부터 연속된 0의 개수를 출력합니다.

 

▣ 입력 예시

12

▣ 출력 예시

2

 

 

-내 코드

#include <stdio.h>

int main()
{
    int N;
    int fac=1;
    scanf("%d", &N);
    
    for(int i = 1; i <=N; i++){
        fac *= i;
    }
    
    int now = fac;
    int zeros = 0;
    int max = 0;
    while(1){
        if(now%10==0){
            zeros++;
            if(zeros > max) max=zeros;
        }
        else zeros = 0;
        now /=10;
        if(now==0) break;
    }
    
    printf("%d", max);

    return 0;
}

결과는 잘 나오나 시간복잡도면에서 효율적이지 않다.

 

 

새로운 접근방법

N!의 결과값에 0이 있다는 뜻은 10 또는 2와 5로 나눌 수 있다는 것으로 해석할 수 있다.

소인수분해를 했을 시, 2와 5의 개수를 비교하고 더 적은 수를 출력하면 된다. 

 

120! = 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 2*2*3 * 11 * 2*5 * 3*3 * 2*2*2 * 7 * 2*3 * 5 * 2*2 * 3 * 2

2 개수: 10개, 5 개수: 2개

따라서 2이다. 

 

-고친 코드 

#include <stdio.h>

int main()
{
    int N;
    int twos=0;
    int fives=0;
    scanf("%d", &N);
    for(int i = 2; i <=N; i++){
        int num = i;
        int j = 2;
        while(num!=1){
            if(num%j==0){
                if(j==2) twos++;
                else if(j==5) fives++;
                num/=j;
                j=2;
            }
            else j++;
        }
    }
    if(twos > fives) printf("%d", fives);
    else printf("%d", twos);

    return 0;
}