[백준 BOJ 2004번] 조합 0의 개수

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

2004번: 조합 0의 개수

 

1. 문제

 

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

---

2. 입력

 

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

---

3. 출력

첫째 줄에 (nm)$n \choose m$의 끝자리 0$0$의 개수를 출력한다.

---

4. 풀이

어떤 숫자의 끝자리부터 연결되는 0을 만드는 건 이전에도 풀었다시피 2와 5의 조합으로 생성되는 것이다. 따라서 구하고자 하는 조합에서 남는 2와 5의 개수를 구해주면 된다. 물론 조합식이 모두 계산이 끝나고서 그 값을 2와 5로 나눠보면 안되고 그 중간에서 캐치해내야 한다.

---

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(), " ");

        long n = Integer.parseInt(st.nextToken());
        long m = Integer.parseInt(st.nextToken());
        long five = check(n,5) - check(m,5) - check(n-m,5);
        long two = check(n,2) - check(m,2) - check(n-m,2);
        long a = (five>two)?two :five;
        System.out.println(a);

    }

    public static long check(long a, long b){
        long count = 0;
        while(a>=b){
            count += a/b;
            a /= b;
        }
        return count;
    }
}

---

6. 배운 것

처음에 문제를 접근할 때 최대한 계산량을 줄여보고자 10C6을 10C4로 바꾸는 등 조합식 계산에 쓰이는 숫자를 줄이고자 했다. 하지만 이는 결국 조합식을 만들어내기에 문제가 있었다. 조합이 단순히 5C2 = 5*4/2*1이 아니라 5!/(2!*(5-2)!)이란 것을 안다면 모든 값들이 ....*2*1로 끝나기에 접근이 쉬웠을 것 같다. 조합에서 소인수 분해를 하는 방법과 조합식이 하나만이 아니란 것을 배웠다.