[BOJ 2004번] 조합 0의 개수(JAVA)

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

2004번: 조합 0의 개수

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int[] number;
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		long n=Long.parseLong(s[0]);
		long m=Long.parseLong(s[1]);
		if(n==m||m==0) {
			System.out.println(0);
			return;
		}
		int numberof2=0, numberof5=0;
		for(long i=2;i<=n;i*=2) {
			numberof2+=n/i;
		}
		for(long i=2;i<=m;i*=2) {
			numberof2-=m/i;
		}
		for(long i=2;i<=n-m;i*=2) {
			numberof2-=(n-m)/i;
		}
		for(long i=5;i<=n;i*=5) {
			numberof5+=n/i;
		}
		for(long i=5;i<=m;i*=5) {
			numberof5-=m/i;
		}
		for(long i=5;i<=n-m;i*=5) {
			numberof5-=(n-m)/i;
		}
//		for(long i=2;i<=n;i++) {
//			long temp=i;
//			while(true) {
//				if(temp%2==0) {
//					numberof2++;
//					temp/=2;
//				}
//				else if(temp%5==0) {
//					numberof5++;
//					temp/=5;
//				}
//				else break;
//			}
//		}
//		for(long i=1;i<=m;i++) {
//			long temp=i;
//			while(true) {
//				if(temp%2==0) {
//					numberof2--;
//					temp/=2;
//				}
//				else if(temp%5==0) {
//					numberof5--;
//					temp/=5;
//				}
//				else break;
//			}
//		}
//		for(long i=1;i<=n-m;i++) {
//			long temp=i;
//			while(true) {
//				if(temp%2==0) {
//					numberof2--;
//					temp/=2;
//				}
//				else if(temp%5==0) {
//					numberof5--;
//					temp/=5;
//				}
//				else break;
//			}
//		}
		long result=Math.min(numberof2, numberof5);
		System.out.println(result);
	}

}

조합(Combination) 공식은 아래와 같습니다.

앞선 1676번 문제에서 팩토리얼 0의 개수 구하기 문제에서 사용했던 방법과 비슷하게 접근할 수 있습니다.

https://eloquence-developers.tistory.com/56

[BOJ 1676번] 팩토리얼 0의 개수(JAVA)

분자 부분의 n!의 2와 5의 소인수의 개수를 구해 10의 소인수의 개수를 구하고, 분모 부분의 (n-r)!과 r!에서 2와 5의 소인수의 개수를 구해 10의 소인수의 개수를 뺴주면 0의 개수를 구할 수 있습니다.

그래서 numberof2에 1부터 n까지 2의 몇 제곱인지를 구해서 numberof2에 더하고, 1부터 n-r과 1부터 r까지 2의 몇 제곱인지를 구해서 numberof2에서 빼면 nCr이 2이 몇 제곱인지를 구합니다.

비슷한 방식으로 numberof5에 n!에서 1부터 n까지 5의 몇 제곱인지를 구해 numberof5에 더하고, 1부터 n-r과 1부터 r까지 5의 몇제곱인지를 구해서 numberof5에서 빼서 nCr이 5의 몇 제곱인지를 구합니다.

이를 통해 numberof2와 numberof5 중 작은 값이 10의 몇 제곱인지 이므로, 이 것이 0의 개수가 됩니다.

처음에 제가 주석 처리를 해놓은 코드로 풀었는데 시간 초과가 발생해서 주석처리가 되지 않은 부분으로 풀어야합니다.