(JAVA) 백준 2004번 : 조합 0의 개수

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

2004번: 조합 0의 개수

이번 문제는 nCr 을 DP를 이용하여 구한 후, 누적합을 구하는 방식으로 풀이했다가 메모리 에러가 발생하여 밑의 글을 참고하여 풀이를 진행하였습니다.

항상 잘 보고 있습니다 : )

 

https://st-lab.tistory.com/166

[백준] 2004번 : 조합 0의 개수 - JAVA [자바]

 

하나하나 해결해보자!

우선 nCr 은 n!/(n-m)!m! 로 정의할 수 있다.

그리고 

n! = 2^a1*5^a2

n-m! = 2^b1*5^b2

m! = 2^c1*5^c2

와 같이 소인수를 정의할 수 있고 n!/(n-m)!m! 에 적용하면 2^(a1-b1-c1) X 5^(a2-b2-c2) 라는 결론이 나온다.

 

자세한 풀이는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main 
{ 
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		// 입력 값이 20억이 넘기 대문에 long 사용
		long N = Long.parseLong(st.nextToken());
		long M = Long.parseLong(st.nextToken());

		/*
		 * 누적합을 구하는 이유는 50!으로 예를 들면 50,45,40 .. 이렇게 5의 배수마다 5의 승수가 증가하기 때문에
		 * 1 - 50까지의 승수! 즉, 5의 배수가 반복되는 수의 합을 구하는 것이다.
		 */
 
		/*
		 * n!/(n-m)!m! 에 대한 승수를 아래와 같이 구한다.
		 */
		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);

		// 2와 5 중의 최소 값 만큼 10이 만들어진다.
		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;
	}
}