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

2004번: 조합 0의 개수

 

문제

풀이

바로 전 문제인 "팩토리얼 0의 개수" 문제와 비슷한데, n의 범위가 많이 커졌다.

시간초과가 발생할 것 같았지만, 혹시나 해서 같은 방법으로 제출해 보았는데 역시나였다.

혼자 해결이 안 돼서 구글링을 해보았고, 필자가 이해한 방법은 아래와 같다.

 

어떤 숫자의 끝자리 0의 개수를 구하려면, 해당 숫자에 2가 몇 개 있는지, 5가 몇 개 있는지 알아야 한다.

2의 개수와 5의 개수를 안다면 둘 중 작은 값이 0의 개수가 되기 때문이다.

 

하지만 그 개수를 구하는 것이 어려웠다.

10! 에서 2의 개수를 구하는 예를 들어 보겠다.

 

10! 은 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10이다.

여기서 10을 2로 나누면 5가 되는데, 5는 2의 배수의 개수가 된다.

여기서 5를 2로 나누면 2가 되는데(5 / 2 = 2), 2는 4의 배수의 개수가 된다. * ( 10 / 2 ) / 2 = 10 / 4 이므로 4의 배수의 개수가 된다.

여기서 2를 2로 나누면 1이 되는데, 1은 8의 배수의 개수가 된다. * { ( 10 / 2 ) / 2 } / 2= 10 / 8 이므로 8의 배수의 개수가 된다.

여기서 1을 2로 나누면 0이 되는데, 0은 16의 배수의 개수가 된다. (16의 배수는 없다)

 

2의 배수는 2를 1개 가지고 있고, 4의 배수는 2를 2개, 8의 배수는 2를 3개 가지고 있다.

 

10! 은 2의 배수를 5개, 그중 4의 배수를 2개, 그중 8의 배수를 1개 가지고 있다.

따라서 10! 은 5 + 2 + 1 = 8개의 2를 가지고 있다는 것을 알 수 있다.

 

아래 코드의 countN 함수가 위 과정을 구현한 함수이다. (위 예시에서 num = 10, N = 2)

 

이 함수를 구현하고, nCm = nPm / m! = n! / { (n - m)! * m! } 임을 이용하여 문제를 해결하였다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int count2 = countN(n, 2) - countN(n - m, 2) - countN(m, 2);
        int count5 = countN(n, 5) - countN(n - m, 5) - countN(m, 5);

        int result = Math.min(count2, count5);
        System.out.println(result);
    }
    public static int countN(int num, int N) {
        int count = 0;
        while(num != 0) {
            count += num / N;
            num /= N;
        }
        return count;
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!