[백준] 2004 : 조합 0의 개수 JAVA 풀이

 

 

팩토리얼 0의 개수 문제와 유사한 문제였다.

 

뒷자리가 0이라는 건 2와 5가 곱해졌다는 뜻이므로

분모와 분자가 서로소일 때

분자에 남은 2와 5가 짝을 이루는 쌍의 개수가 몇개인지 세면 되겠다는 생각이 들었다.

 

N = 25, M = 12 가 입력됐을 경우

분자는 25 ~ 25-12+1인 14까지를 곱한 값

분모는 12부터 1까지를 곱한 값이 된다.

 

twoCnt = 분자의 2의 개수 - 분모의 2의 개수 - 필요없는 구간의 2의 개수

fivecnt = 분자의 5의 개수 - 분모의 5의 개수 - 필요없는 구간의 5의 개수

두 개의 값을 구한 뒤 더 작은 값을 출력하도록 했다.

(여기서 필요없는 구간이란 25~14 이외의 구간이다.)

 

두 개의 값 중 더 작은 값을 구하는 이유는,

2와 5가 짝을 이룰 때 뒷자리가 0이 되니 그 짝을 이루는 쌍의 개수를 구하기 위해서이다.

예를 들어 2*5*5라는 식이 있을 때

2와 5가 짝을 이루는 쌍의 개수는 하나뿐이다. 

즉 twoCnt = 1, fiveCnt = 2이니 1이 출력될 것이다.

 

 

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

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(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int twoCnt = get(N,2)-get(M,2)-get(N-M,2);
        int fiveCnt = get(N,5)-get(M,5)-get(N-M,5);
        
        System.out.println(Math.min(twoCnt, fiveCnt));
        
    }
    
    public static int get(int a, int b) {
    	int tmp = 0;
    	while(a>=b) {
    		tmp += a/b;
    		a /= b;
    	}
    	return tmp;
    	
    }
    
    
}

 

직접 푼 문제인데도 문제를 어떻게 풀었는지 설명하는 게 정말 어렵다.....