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

## 💡문제

### [Silver II] 조합 0의 개수 - 2004
[문제 링크](https://www.acmicpc.net/problem/2004)
 
#### 성능 요약  
메모리: 11564 KB, 시간: 76 ms  

---
#### [깨진 부분은 여기에서 확인](https://velog.io/@dksek3050/%EB%B0%B1%EC%A4%80-Java-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98%EC%A0%95%EC%88%98%EB%A1%A0)


## 🤔접근법

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

- 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로 각각 몇번 나누어 떨어지는지 구해야한다.

후  분자에서 나온 (2*5) 횟수에서 분모에서 나온 (2*5) 횟수를 빼주면 끝자리 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의 갯수이다.

➡️ 해당 풀이법의 시간 복잡도 : 정확히는 모르겠으나  2와 5를 구하는 과정은 거듭제곱씩 커지기 때문에$O(logN)$ 보다 작을 것이라고 예상된다.

2^30 = 10억

---

## 🤯FAIL

### 범위 오류

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

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

범위를 잘보자..

## 😎SUCCESS

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

---

## 👩‍💻 코드

```java
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;
    }
}
```