[백준 1407] 2로 몇 번 나누어질까 (자바)

백준 1407번: 2로 몇 번 나누어질까? (팩토리얼)

문제 설명

팩토리얼 계산 시, 주어진 수의 팩토리얼 값에서 특정 숫자로 나눠질 수 있는 횟수를 구하는 문제입니다. 예를 들어, (10!)의 경우 2로 나누어질 수 있는 횟수를 구하는 방법을 설명합니다.

문제 접근 방법

1. 팩토리얼의 정의: 팩토리얼 (N!)은 1부터 (N)까지의 모든 정수를 곱한 값입니다.
2. 팩토리얼의 소인수 분해: (N!)에서 특정 소수 (p)의 거듭제곱으로 몇 번 나눌 수 있는지를 구하는 문제입니다.
3. 나누어지는 횟수 계산: (N!)에서 (p)의 지수는 (\left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \cdots)의 합으로 계산할 수 있습니다.

시간 복잡도 분석

O(log_b N)

• func 함수에서 Math.pow(digit, i)는 ( \log_b{N} )만큼 반복하여 (N)을 나누는 과정이 수행됩니다.
• 따라서 전체 시간 복잡도는 (O(\log_b N))입니다.

해결 방법

아래는 주어진 범위에서 팩토리얼을 특정 숫자로 나눠질 수 있는 횟수를 구하는 Java 코드입니다:

package re_02;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1407_2로몇번나누어질까_팩토리얼_3트 {
    /**
     * 팩토리얼, 10! 이라 했을때, 2로 나눠가면서 2가 몇개 포함되어있는지를 알수있다.
     * 10//2=5  10//4=2.xxx 10//8 1.xxx 5+2+1 8개
     * <p>
     * 함수의 정의
     * 1 1 1 1 1 1 1 1 1 1 2^0 1은 모두 포함하니 더해줬다고 가정
     * 10//2^1 * 2^1 - 2^0
     * 10//2^2 * 2^2 - 2^1
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken()); //5
        long b = Long.parseLong(st.nextToken()); //9

        int digit = Integer.parseInt(st.nextToken()); //2
        long answer = func(b, digit) - func(a - 1, digit);

        System.out.println(answer);
    }

    private static long func(long n, int digit) {
        long result = 0;
        result += n;
        for (int i = 1; i < 1000000; i++) {
            if (n / Math.pow(digit, i) < 1) {
                break;
            }
            long sum = (n / (long) Math.pow(digit, i) * ((long) Math.pow(digit, i) - (long) Math.pow(digit, i - 1)));
            result += sum;
        }
        return result;
    }
}