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

💡문제

[Silver II] 조합 0의 개수 - 2004

문제 링크

성능 요약

메모리: 11564 KB, 시간: 76 ms

---

🤔접근법

범위 체크 및 시간복잡도 예상

• 0 ≤ m ≤ n ≤ 2,000,000,000 (20억) n ≠ 0
• $O(\sqrt N)$ 또는 $O(logN)$ 이어야 한다.

풀이법

⭕ 접근 방법

끝자리가 0으로 끝나기 위해서는 어떤수에 곱하기 10을 해야하고 이 의미는 (2 *5)를 소인수로 가지고 있다는 의미가 된다.

그래서 nCm의 값이 2로 몇번 나누어 떨어지고 5로 몇번 나누어 떨어지는지 구해 (2*5)를 몇번 포함하고 있는지 구하면 된다.

$_nC_m = \frac{n!}{(n-m)!m!}$ 이므로 각 팩토리얼들이 2 와 5로 각각 몇번 나누어 떨어지는지 구해야한다.

후 분자에서 나온 (25) 횟수에서 분모에서 나온 (25) 횟수를 빼주면 끝자리 0의 개수가 나올 것이라고 생각했다.

1. n! 에서 2와 5로 각각 몇번 나누어 떨어지는지 구하기 → (2*5) 를 몇번 포함하는지 구하기
2. (n-m)! m! 에서 2로 몇번 나누어 떨어지는지 구하기
3. (n-m)! m! 에서 5로 몇번 나누어 떨어지는지 구하기
4. 2와 5가 각각 분모보다 분자가 더 큰지 확인
   • 크지 않다면 10을 만들수 없으므로 결과는 0
5. 2와 5의 횟수 중 작은 수가 10의 갯수 이므로 0의 갯수이다.

시간복잡도에 가장 큰 영향을 미치는 부분은 n!을 소수 x로 몇번 나누어 떨어지는지 구하는 부분이다. 이를 코드로 작성하면 아래와 같다.

//x를 k로 몇번 나누어 떨어지는 구하는 함수
    private static int divisionCnt(int x, int k) {
        int cnt = 0;
        long divisor = k;
        while (divisor <= x){
            cnt += x / divisor;
            divisor *= k;
        }
        return cnt;
    }

➡️ 해당 풀이법의 시간 복잡도 : $O(log_kx)$ 반복될 수록 1/k씩 탐색범위가 줄어들기 때문

정확히는 모르겠으나 2와 5를 구하는 과정은 거듭제곱씩 커지기 때문에$O(logN)$ 보다 작을 것이라고 예상된다.
2^30 = 10억 정확히 몰랐지만 스터디 덕분에 알게 되었다. 👍

---

🤯FAIL

범위 오류

2 또는 5로 몇번 나누어 떨어지는지 구하는 과정에서

2 또는 5가 거듭제곱 되는 과정에서 int 과정을 넘어가 런타임에러가 떴다.

범위를 잘보자..

😎SUCCESS

생각한 시간복잡도와 로직은 맞게 판단하였다.

---

👩‍💻 코드

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

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 분자는 n!
        int numerator2 = divisionCnt(n,2);
        int numerator5 = divisionCnt(n, 5);

        // 분모는 (n-m)! m!
        // 2로 나누어 떨어지는 횟수는 (n-m)!에서의 2로 나누어 떨어지는 횟수 + m에서 2로 나누어 떨어지는 횟수
        // 5로 나누어 떨어지는 횟수는 (n-m)!에서의 5로 나누어 떨어지는 횟수 + m에서 5로 나누어 떨어지는 횟수
        int denominator2 = divisionCnt(n-m, 2) + divisionCnt(m, 2);
        int denominator5 = divisionCnt(n-m,5) + divisionCnt(m, 5);

        int result2 = numerator2 - denominator2;
        int result5 = numerator5 - denominator5;

        if(result2 <= 0 || result5 <= 0){
            System.out.println("0");
            return;
        }else{
            System.out.println(Math.min(result2, result5));
        }

    }

    //x를 k로 몇번 나누어 떨어지는 구하는 함수
    private static int divisionCnt(int x, int k) {
        int cnt = 0;
        long divisor = k;
        while (divisor <= x){
            cnt += x / divisor;
            divisor *= k;
        }
        return cnt;
    }
}