[수학] 백준 1676 - 팩토리얼 0의 개수

문제본문

문제 해석

입력으로 들어오는 N!의 결과 값에서 뒤에서 부터 0이 아닌 숫자가 나올때까지 0의 개수를 구하라

문제를 이해하는 데 시간이 필요했다. 결론적으로 말하면 N!의 결과 값이 301200라고 한다면 뒤에서 부터 0이 2번 나오고 그 다음으로 2가 나온다. 따라서 0이 아닌 숫자가 나올 때까지 0의 개수는 2라고 답할 수 있다.


문제에서 주어지는 N의 범위는 0 <= N <= 500이다. N!으로 계산했을 때 30이 입력값으로 들어와도 N!의 값은 어마어마하게 커지는 것을 알 수 있다. 따라서 int 또는 long의 표현 가능한 숫자 범위를 생각했을 때, N!의 결과 값을 구한 후 0의 개수를 세는 것은 거의 불가능이다. (물론 무한대 정수인 BigInteger를 사용하면 가능은 한 것 같다. 하지만 비효율) 그래서 소인수 분해 성질을 이용해 N!에서 곱해지는 수에 대해 비교를 시작한다.

 

첫번째 방법 - 5와 2 의 개수 구하기

숫자 뒤에 0이 있다는 것은 10이 곱해져 있는 것이다. 320 = 32 x 10, 301200 = 3012 x 10 x 10 처럼 10이 곱해지는 횟수를 구하면 된다. 10은 2와 5의 곱으로 이루어지므로 두 수의 개수의 최소 값이 10이 곱해지는 횟수가 된다!

        int twoCount = 0;
        int fiveCount = 0;

        for (int i = 1; i <= n; i++) {

            int number = i;
            while (number != 0 && number % 2 == 0) {
                number = number / 2;
                twoCount += 1;
            }

            while (number >= 5 && number % 5 == 0) {
                number = number / 5;
                fiveCount += 1;
            }
        }

        System.out.println(Math.min(twoCount, fiveCount));

 

 

두번째 방법 - 5의 개수 구하기

다른 사람의 풀이를 알고 난 방법, 첫번째 방법에서 우리는 2와 5의 개수로 10이 곱해지는 횟수를 유추할 수 있다고 판단했고 2와 5의 개수를 구하기 위해 1 부터 n까지 비교했다. 하지만 2는 짝수이기 때문에 N!의 소인수에서 5 개수보다 적을 수가 없다. 따라서 5의 개수만 구하면 된다.

 

그럼 5의 개수를 첫번째 방법과 똑같이 구하면 될까? 5의 개수는 구할 수 있지만 위 방법은 비효율적이다.

 

int count = 0;

while (n > 0) {
   count = n / 5;
   n /= 5;
}

System.out.println(count);

 

 

놀랍게도 정말 많이 코드가 줄어들었다. 해당 코드의 해석을 보자. 우린 N!의 소인수 중 5의 개수가 0의 개수란 사실을 알고 있다.

N = 10일때, 0의 개수는 2. 10! = 10(5 x 2) x 9 x 8 x 7 x 6 x 5 x 4 x ..
N = 25일때, 0의 개수는 6, 25! = 25(5 x 5) x 24 x 23 ... x 21 x 20(5 x 4) x 19 x .. x 14 x 15(5 x 3) x 13 x.. 10(5 x 2) x 9 x .. 5.. x 1

 

위의 관계를 보았을 때, N의 값에서 5를 나눈 몫이 N ~ 1까지의 범위에서 5가 나올 개수를 의미한다.