[백준_2004번] 조합 0의 개수

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

2004번: 조합 0의 개수

[문제]

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

/*
 * 이항 계수를 구하는 공식은 nCm = n! / (n-m)! * m! 이다.
 * 0은 2와 5의 곱으로 만들어지기 때문에 n!에서의 2와 5의 개수에서
 * (n-m)! * m!에서 만들어지는 2와 5의 개수를 빼주면 된다. 
 * 지수는 나눗셈인 경우 뺄셈으로 계산하기 때문이다.
 * 이렇게 구해진 5와 2의 개수 중 작은 숫자가 문제의 해답이 된다.
 */
public class BaekJoon_2004 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		long N=sc.nextLong();
		long M=sc.nextLong();
		
		 //n!에서의 2와 5의 개수에서 (n-m)! * m!에서 만들어지는 2와 5의 개수를 빼준다.
		long count5=five_power_n(N)-five_power_n(N-M)-five_power_n(M);
		long count2=two_power_n(N)-two_power_n(N-M)-two_power_n(M);
        
		// 5와 2의 개수 중 더 작은 값을 출력해야 그 만큼 0이 만들어진다.
		System.out.println(Math.min(count5,count2));
	}
	
	// 5의 승수를 구하는 함수 
	static long five_power_n(long num) {
		int count = 0;
		// 숫자를 5로 나눠 5의 개수를 구해준다.
		while(num>= 5) {
			count+=(num/5);
			num/=5;
		}
		return count;
	}
		
	// 2의 승수를 구하는 함수
	static long two_power_n(long num) {
		int count = 0;
		// 숫자를 2로 나눠 2의 개수를 구해준다
		while(num >= 2) {
			count+=(num/2);
			num/=2;
		}
		return count;
	}
}

[고찰]

 이번 문제는 이전의 팩토리얼의 0의 개수를 구하는 것과 비슷한 문제였다. 끝자리 0의 개수는 2와 5의 곱의 개수로 결정된다. 따라서 nCm = (n!) / (n-k)! * k! 에서 2와 5의 승수를 구한 후 그 중 최솟값을 찾아야 한다. 이때 지수는 나눗셈을 뺼셈으로 계산하기 때문에 n!에서의 2와 5의 개수에서 (n-m)! * m!에서 만들어지는 2와 5의 개수를 빼주면 된다. 유도된 식은 아래 그림과 같다.

[출처 : https://st-lab.tistory.com/166]