[C] 백준_1676번

팩토리얼 0의 개수 (silver 4)

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

 

입력

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

 

출력

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

 

 

예시 입력 1

10

예시 출력 1

2

 

 

 

입력한 수를 뒤집어서 뒤에서부터 0의 개수를 세면 어떨까..라는 생각을 처음에 했었는데 C언어로는 파이썬보다 이를 구현하기가 쉽지 않을 것 같아서 다른 방법을 생각해봤다.

0은 결국 10의 배수 즉, 2와 5의 곱을 통해 만들어지기 때문에 이를 이용했다.

 

10 팩토리얼을 예시로 들어보자.

 

N! = 1 x 2 x 3 x ... x N

ex) 10! = 3628800

10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

10! = 1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x (2 x 5)

10! = 2^8 x 3^4 x 5^2 x 7

10! = (2^2 x 5^2) x 2^6 x 3^4 x 7

10! = 10^2 x 2^6 x 3^4 x 7

이를 통해 알 수 있는 건 2와 5의 개수 중 작은 것이 곧 0의 개수라는 것이다.

 

 

따라서 다음과 같이 코드를 작성해주었다.

#include <stdio.h>

int main() {
    int num;
    int two = 0, five = 0;
    
    scanf("%d", &num);
    for (int i = 2; i <= num; i *= 2){
        two += num / i;
    }
    for (int j = 5; j <= num; j *= 5){
        five += num / j;
    }
    printf("%d\n", (two < five)? two : five);
    
    return 0;
}

설명)

num을 정수형 변수로 선언하고, num을 소인수분해 했을 때 나오는 2의 배수의 개수를 two라고 하고, num을 소인수분해 했을 때 나오는 5의 배수의 개수를 five라고 해주었다.

for문을 통해 two에 num을 2의 배수 i로 나눠준 몫을 더해주었고, 마찬가지로 five에도 num을 5의 배수 j로 나눠준 몫을 더해주었다.

마지막으로 삼항연산자를 사용해서 two와 five 중에 작은 값을 출력하도록 해주었다.

 

 

참고 : https://ksj14.tistory.com/entry/BackJoon1676-팩토리얼-0의-개수