[JAVA] 백준 (실버2) 2004번 조합 0의 개수

링크

https://www.acmicpc.net/problem/2004

---

문제 설명

(정답률 28.726%)

$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.

---

입력 예제

25 12

---

출력 예제

2

---

정답 코드

1. 조합의 공식은 다음과 같다
   $nCr$ = $n \choose m$ = $\frac {n!} {(n-m)!*m!}$
2. 끝자리 0의 개수를 구하는 것은 결국 소인수로 10을 몇개나 가지고 있는지 구하는 것이다.
3. 10의 소인수는 2, 5이므로 2와 5의 개수중 작은게 문제의 정답이 된다.
4. 팩토리얼의 특정 소인수 개수를 구할 때는 다음과 같이 한다.
   가령 52!의 5의 개수를 구한다고 하면 ($52! = 52*51*50 * ···*3*2*1$)
   52를 5로 나누면 10이 되는데 이는 $52!$에서 5를 소인수로 가지는 수의 개수이다. (5, 10, 15, ···, 40, 45, 50)
   여기서 다시 5를 나누면 2가 되는데 이는 1, 2, 3, ···, 8, 9, 10 중에 5를 소인수로 가지는 수의 개수가 된다. (5, 10)
   나눈 수를 더하면 12(10+2)가 되고 이건 52!의 5의 개수가 된다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int twoCnt = 0;		//2의 개수
        int fiveCnt = 0;	//5의 개수

        twoCnt = getCnt(n, 2) - getCnt(m, 2) - getCnt(n - m, 2);
        fiveCnt = getCnt(n, 5) - getCnt(m, 5) - getCnt(n - m, 5);
        
		//2의 5의 개수 중 작은 것 출력
        System.out.println(Math.min(twoCnt, fiveCnt));
    }

	//num!의 countNum의 개수를 구하는 메소드
    static int getCnt(int num, int countNum) {
        int cnt = 0;

        while (num >= countNum) {
            cnt += num / countNum;
            num /= countNum;
        }

        return cnt;
    }
}

---

정리

처음엔 조합 공식이 팩토리얼로 이루어 지므로 팩토리얼 메소드를 정의하고,
조합 결과를 직접구해서 단순히 끝 0의 개수를 카운트하려 했는데
입력값으로 주어지는 n과 m의 최대값이 20억이라..
거기다 계속 재귀 함수를 호출해서 직접 조합의 결과값을 구하려는건
무조건 메모리 초과가 날 수 밖에 없었다.
그래서 도저히 아이디어가 생각이 나질 않아서 구글링을 했는데
팩토리얼의 연산을 하지 않아도 특정 소인수를 개수를 세는 방법이 있었다.
확실히 수학에 관련된 문제는 수학을 잘하면 유리한 거 같다..