[백준알고리즘] 2004번: 조합 0의 개수 -Java

[백준알고리즘] 2004번: 조합 0의 개수 -Java

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

2004번: 조합 0의 개수

 

이전 문제였던 팩토리얼 0의 개수와는 조금 다르다.

 

팩토리얼 0의 개수 문제에서는 5로 나누고 5의 제곱으로 나누고 했던 이유는 5 이전에 이미 2가 존재해서 10이 당연히 되기 때문에 5의 제곱수들로만 풀어도 가능했다.

 

하지만 이항계수에서는 분자를 분모로 약분할 수 있기 때문에 2의 존재 가능성의 여부도 따져줘야 한다.

 

 

즉 약분을 했을 때 10을 몇 개나 곱하느냐를 구하면 되는 문제이다. 따라서 5의 개수와 2의 개수를 각각 구해주고 둘 중의 최소 개수만큼 10을 곱하게 된다는 점을 이용해서 각각을 계산해주면 된다.

 

이항 계수는 nCm = n! / (m! * (n - m)!) 이기 때문에 n! 에서의 5와 2의 개수에서 m! 와 (n-m)! 에서의 5와 2의 개수들을 모두 빼주면 된다.

 

 

아 그리고 아이디어는 일찍이 생각했었는데.... 계속 맞는데 왜 자꾸 런타임 에러라고 뜨지.... 하다가 maximum 범위인 2000000000C10을 해봤는데 ArithmeticException이 발생했다. 보니 / by zero가 떴는데, 분명 2를 명시해서 인자로 넣어줬는데도 에러가 발생했다. 그래서 int의 범위를 벗어났다고 생각해서 long으로 바꿔서 겨우 풀었다.

 

그런데 int의 범위는 2,000,000,000 보다 크지 않나..? 이유 아시는 분 계시면 알려주세요ㅠㅠ

 

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

public class Main {
	
	public static long how_many(long t, long d) {
		long ret = 0;
		long dt = d;
		while(t >= dt) {
			ret += (t / dt);
			dt *= d;
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		long n, m;
		long d5 = 5, d2 = 2;
		long num_5, num_2;
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		
		// n의 5의 개수와 2의 개수
		num_5 = how_many(n, d5);
		num_2 = how_many(n, d2);
		
		// m의 5의 개수와 2의 개수
		num_5 -= how_many(m, d5);
		num_2 -= how_many(m, d2);
		
		// n-m의 5의 개수와 2의 개수
		num_5 -= how_many(n-m, d5);
		num_2 -= how_many(n-m, d2);
		
		System.out.println(num_5 > num_2 ? num_2:num_5);
		return;
	}

} 

 

방법은 금방 찾았었는데.. 오랜만에 자바로 제출하려니까 자꾸 형식을 이상하게 내고... 버거웠다 ㅠㅠ

수학 3의 문제도 벌써 다 풀었다!!

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다