[백준] JAVA 자바 : 팩토리얼 0의 개수 (1676번)

숫자 N이 주어지면, N!의 맨 뒷자리부터 돌면서 연속된 0의 개수를 구하는 문제이다.
이 알고리즘을 일일이 N마다 팩토리얼을 다 구하려고 하면 오버플로우가 발생한다. N의 최대값이 500인데, 500!은 엄청나게 큰 수이기 때문…
그렇기 때문에 팩토리얼을 구하려면 BigInteger을 쓰거나 해야 하는데 사실 BigInteger은 내 취향이 아니라서 그냥 다른 방법을 고안했다.

처음 고안한 방법은 1부터 N까지 돌면서, 그 수의 약수 중 2, 5, 10이 몇 개 들어가는지 구하는 방법이다.
기본적으로 뒷자리의 0은 약수 중 10이 포함된 개수일 테니 약수 중 10의 개수를 먼저 찾은 다음 5와 2의 개수 중 작은 수를 더해주면 연속된 0의 개수가 나온다.

그런데 여기서 조금 더 생각해보면, 10은 5가 반드시 포함된다. 따라서 약수 중 10의 개수는 셀 필요가 없다는 뜻이다. 왜? 어차피 약수 중 5의 개수를 세면 자동으로 10의 개수가 세어지기 때문…
조금만 더 생각해보면 2의 개수도 셀 필요가 없다. 어차피 2가 얼마나 있던 간에 5가 있어야 10이 만들어지기 때문이다. 통상적으로 약수의 개수는 5보다 2가 더 많기 마련이니… 사실상 약수 중 5의 개수만 세면 그게 연속된 0의 개수가 될 것이다.

ㅋㅋ 사실 나는 처음 고안한 방법으로 알고리즘을 짜서 통과했는데, 다른 분들 코드를 조금 참고해보니 5만 세어도 된다는 사실을 그 때 깨달았다… 아직 나는 이 정도에 불과하구나 ㅋㅅㅋ

 

package BJoon.수학1;

import java.io.*;

public class FactorialFindZero_1676 {
    static int num5 = 0; // 해당 수가 가진 약수 5의 개수
    
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static int findZero(int N) {
        for (int i=1; i<=N; i++) { // 1부터 N까지 돌면서
            int tmp = i;
            /*while (true) { // 그 수의 약수 중 2, 5, 10이 포함되는지 찾는다
                if (tmp % 10 == 0) { // 만약 약수에 10이 포함된다면
                    num10++; // 10의 개수를 올려준다
                    tmp /= 10;
                    continue;
                } else if (tmp % 5 == 0) { // 약수에 5가 포함된다면
                    num5++; // 5의 개수를 올려준다
                    tmp /= 5;
                    continue;
                } else if (tmp % 2 == 0) { // 약수에 2가 포함된다면
                    num2++; // 2의 개수를 올려준다
                    tmp /= 2;
                    continue;
                } else { // 약수에 아무 것도 포함되지 않는다면
                    break; // 반복을 더 할 필요가 없다.
                }
            }
            
        int res = num10; // 기본적으로 뒤에 나오는 0의 개수는 약수 중 10의 개수임
        res += num5; // 거기서 약수에 2 * 5가 몇 번 포함되는지 더해준다. num5보다 num2가 항상 많을 것
        // 이 res를 반환하면 답이 나온다
        */
            
            // 위의 내용을 확인했을 때, 사실 코드는 약수 5의 개수만 확인하면 된다.
            while (tmp % 5 == 0) { // 약수 중 5가 포함되는 수를 구한다
                num5++;
                tmp /= 5;
            }
        }
        
        return num5;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = stoi(br.readLine());
        System.out.print(findZero(N));
        
        br.close();
    }
}

 

로그인

 

 

작성일자: 2023-09-10