[BaekJoon] 2004 조합 0의 개수

1.  문제 링크

2.  문제

요약

• nCm의 끝자리 0의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 n과 m이 주어집니다.
• 출력: nCm의 끝자리 0의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public long getTwoNum(int num) {
		int count = 0;
		while(num >= 2) {
			count += (num / 2);
			num /= 2;
		}
		return count;
	}
	
	public long getFiveNum(int num) {
		int count = 0;
		while(num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		return count;
	}
	
	public long getZeroNum(int big, int small) {
		if(small > big / 2) {
			small = big - small;
		}
		long two = getTwoNum(big) - getTwoNum(small) - getTwoNum(big - small);
		long five = getFiveNum(big) - getFiveNum(small) - getFiveNum(big - small);
		long count = Math.min(two, five);
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		StringTokenizer st = new StringTokenizer(input);
		int big = Integer.parseInt(st.nextToken());
		int small = Integer.parseInt(st.nextToken());
		Main m = new Main();
		bw.write(m.getZeroNum(big, small) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 조합(nCm)은 다리 놓기 문제에서 무엇인지 설명하고 있습니다.
• 뒷자리 0의 개수는 2와 5의 겹치는 제곱되는 수와 같습니다.
• nCm = n! / (n-r)!r! 공식을 이용하여 n!, (n-r)!, r!의 2와 5의 제곱되는 개수를 구한 후 n! - (n-r)! - r!을 통해 nCm을 했을 때의 2의 제곱되는 개수와 5의 제곱되는 개수를 구합니다.
• 2와 5의 겹치는 제곱되는 수를 구해야 하므로 구한 2와 5의 제곱되는 개수 중 더 작은 수가 뒷자리 0의 개수가 됩니다.