백준2004

2004번: 조합 0의 개수 (acmicpc.net)

2004번: 조합 0의 개수

문제이해

이 문제는 문제를 이해하지 못해 검색을 통해 문제를 이해 했다.

해당 문제의 경우 조합 중 0이 나오는 조합을 찾는 문제이다.

공식은 다음과 같다.

이 공식을 이용해 문제를 풀면 된다.

우선 0이 나오기 위해선 2와 5의 겹치는 승수가 0이 나올 수 있다.

다음을 보면 좀더 이해 하기 쉬울 것이다.

즉 우리가 구할 것은 n!, (n-m)!, m!의 2와 5의 승수를 구하는 것이다.

 

풀이

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		long N = in.nextLong();
		long M = in.nextLong();
		
		// 각각의 승수를 구해준다.
		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);
        
		System.out.println(Math.min(count5, count2));
		
	}
	
	// 5의 승수를 구하는 함수 
	static long five_power_n(long num) {
		int count = 0;
		
		while(num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		return count;
	}
	
	// 2의 승수를 구하는 함수
	static long two_power_n(long num) {
		int count = 0;
		
		while(num >= 2) {
			count += (num / 2);
			num /= 2;
		}
		return count;
	}
 
}