2004. 조합 0의 개수

앞 문제인 1676번 문제와 비슷한데, 팩토리얼 대신 이항계수가 되었습니다.

원리는 똑같습니다. 소인수 분해해서 2*5 = 10의 곱해진 수를 따져줘야하는데, 앞선 팩토리얼은 무조건 2의 제곱수가 5의 제곱수보다 컸지만, 이 문제는 2와 5를 경합해서 최솟값을 뽑아줘야 합니다. 그거말곤 다 똑같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		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 ans1 = five(n) - five(n-m) - five(m);
		int ans2 = two(n) - two(n-m) - two(m);
		System.out.println(Math.min(ans1, ans2));
				
	}
	
	static int five(int n) {
		int count = 0;
		while (n>=5) {
			count += n/5;
			n /= 5;
		}
		return count;
	}
	
	static int two(int n) {
		int count = 0;
		while (n>=2) {
			count += n/2;
			n /= 2;
		}
		return count;
	}
}