[백준 2004] 조합 0의 개수 (Java)

[백준 2004] 조합 0의 개수 (Java)

출처 : 링크

그냥 조합으로 풀면 시간 안에 해결이 불가능하다.

끝자리 0의 개수만 구하면 되므로 다 계산할 필요가 없다.

일단 조합의 식은 아래와 같다.

nCm = n! / (n-m)! * m!

결국 이 값에서 2의 배수와 5의 배수의 갯수를 찾으면 된다. 2의 배수 1개와 5의 배수 1개가 만나면 10이 되어 끝자리 0 하나가 생기기 때문

주의) 25부터는 5가 두개, 4부터는 2가 2개이므로 반복문을 잘 돌려야 함

5와 2 모두 n!에서 개수를 구해주고, 나눠지는 (n-m)!이랑 m!에서 나오는 개수를 빼주면 된다.

그리고 5와 2 중에 개수 최소값을 출력하면 끝이다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_2004_조합0의개수 {
 
    static long n, k;
 
    static long five, two; // 5와 2의 수 저장할 변수
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        n = Long.parseLong(st.nextToken());
        k = Long.parseLong(st.nextToken());
 
        five = 0;
        two = 0;
 
        five = fiveCount(n);
        two = twoCount(n);
 
        five -= fiveCount(n - k);
        five -= fiveCount(k);
 
        two -= twoCount(n - k);
        two -= twoCount(k);
 
        System.out.println(five <= two ? five : two); // 최소값으로 출력
    }
 
    public static long fiveCount(long n) { // 5의 개수 세기
        long cnt = 0;
 
        for (long i = 5; i <= n; i *= 5) {
            cnt += n / i;
        }
 
        return cnt;
    }
 
    public static long twoCount(long n) { // 2의 개수 세기
 
        long cnt = 0;
 
        for (long i = 2; i <= n; i *= 2) {
            cnt += n / i;
        }
 
        return cnt;
    }
 
}