백준 2004 / 조합 0의 개수

문제

풀이

설명

조합 0의 개수를 푸는 문제는 팩토리얼 0의 개수를 우선 이해하는 것이 필요하다.
팩토리얼 0의 개수
위 링크의 문제를 보면 알겠지만 한 팩토리얼 값에 2와 5의 승수가 겹치는 수를 구하는 것이 관건이다.
팩토리얼에서 0의 개수를 찾는 문제는 2보다 적게 나오는 5의 갯수만 찾아주면 되었다.
하지만 조합에서 구하는 방법은 좀 다르다.
우선 조합 즉, 이항계수의 공식을 생각하면 된다. 이항계수의 공식은 다음과 같다.
여기서 0의 개수는 2와 5의 겹치는 승수와 같고 즉, n!, (n-m)!, m!의 2와 5의 승수를 구해야 한다.
좀 더 쉽게 설명하자면, 여기서 2의 승수(a1 - b1, c1) 와 5의 승수(a2 - b2 - c2) 가 구해졌으면 이제 겹치는(짝지을 수 있는) 개수를 구하면 되므로, 2와 5의 승수 중 최솟값을 출력하면 된다.

코드

import java.util.Scanner;

public class Num2004 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long n = sc.nextInt();
		long m = sc.nextInt();
		
		// 각각 몇 제곱인지 구해준다.
		long count5 = five(n) - five(n - m) - five(m);
		long count2 = two(n) - two(n-m) - two(m);
		
		// 2와 5 중 제곱의 수가 덜나온 함수를 출력한다.
		System.out.println(Math.min(count5, count2));
	}
	//2의 제곱 수를 구하는 함수
	private static long two(long num) {
		int count = 0;
		
		while(num >= 2) {
			count += (num/2);
			num /= 2;
		}
		
		return count;
	}
	//5의 제곱 수를 구하는 함수
	private static int five(long num) {
		int count = 0;
		
		while(num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		
		return count;
	}
}

참고 : https://st-lab.tistory.com/166
출처 : https://www.acmicpc.net/problem/2004