백준 2004 조합 0의 개수 Java: 2와 5의 지수 세기

백준 2004번 ‘조합 0의 개수’는 이항계수 nCm의 끝에 붙는 0의 개수를 구한다. factorial 값을 직접 계산하면 너무 커지므로, 결과를 소인수분해했을 때 2의 지수와 5의 지수 중 작은 값을 구한다.

• 백준 2004번 조합 0의 개수

끝자리 0은 2×5 한 쌍이다

이항계수는 다음과 같다.

nCm = n! / (m! × (n-m)!)

vₚ(x)를 수 x에 소수 p가 몇 번 곱해져 있는지 나타내는 지수라고 하면 다음처럼 뺄 수 있다.

vₚ(nCm) = vₚ(n!) - vₚ(m!) - vₚ((n-m)!)

끝자리 0 하나에는 2와 5가 하나씩 필요하므로 답은 min(v₂, v₅)다. factorial에는 보통 2가 더 많지만, 조합에서는 분모의 지수를 뺀 뒤 두 값을 모두 확인해야 한다.

n!에 p가 몇 개 들어 있는가

n!에서 p의 배수는 최소 한 개의 p를 제공하고, p²의 배수는 하나를 더, p³의 배수는 또 하나를 더 제공한다.

vₚ(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + ...

power를 계속 곱하면 overflow를 신경 써야 하므로, n 자체를 p로 반복해서 나누며 몫을 더하면 안전하다.

Java 코드

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

public class Main {
    private static long countPrimeInFactorial(long number, long prime) {
        long count = 0;

        while (number > 0) {
            number /= prime;
            count += number;
        }

        return count;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        long n = Long.parseLong(tokenizer.nextToken());
        long m = Long.parseLong(tokenizer.nextToken());

        long countTwo = countPrimeInFactorial(n, 2)
                - countPrimeInFactorial(m, 2)
                - countPrimeInFactorial(n - m, 2);
        long countFive = countPrimeInFactorial(n, 5)
                - countPrimeInFactorial(m, 5)
                - countPrimeInFactorial(n - m, 5);

        System.out.println(Math.min(countTwo, countFive));
    }
}

m = 0이나 m = n도 같은 식에서 자연스럽게 0이 나온다. 별도의 branch가 필요 없다.

10분 잠든 뒤 떠오른 아이디어

원문에는 아이디어가 날 듯 말 듯해 누워서 생각하다 약 10분 잠들었고, 일어난 뒤 5의 배수를 나열하면서 풀이가 떠올랐다고 적혀 있다. 5, 10, 15, 20은 5를 하나씩, 25는 두 개, 125는 세 개 제공한다는 pattern에서 n/5 + n/25 + ...를 도출했다.

처음에는 n!의 0을 세는 문제처럼 5의 배수마다 직접 나눴지만, prime power별 몫을 더하면 입력 크기와 관계없이 O(logₚ n)번만 계산한다. 2와 5 두 번을 합해도 시간은 O(log n), 추가 공간은 O(1)이다.

이 문제를 풀며 당시 단계별 정수론·조합론 section을 마쳤고 다음에는 queue와 deque로 넘어가겠다고 남겼다. 최대공약수와 약수를 함께 쓰는 문제는 백준 2981 검문에서 이어진다.

검증 범위

Java source를 수동 검토하고 m = 0, m = n, 작은 조합 값을 직접 계산한 factorial oracle 및 random n ≤ 30 조합과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.