1. 문제 링크
https://www.acmicpc.net/problem/2004
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의 개수가 됩니다.