[BaekJoon] 2004번 - 조합 0의 개수 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 이항계수에서 끝자리 0의 개수를 세는 문제로 조합을 팩토리얼로 바꾸어 찾으면 해결할 수 있다.

이항계수는 아래와 같이 팩토리얼간 나눗셈으로 바꿀 수 있다.

\[\binom{n}{m} = \frac{n!}{m!(n-m)!}\]

끝자리에 0이 있다는 것은 위 식에서 분자와 분모에 소인수로 있는 2와 5의 개수를 각각 세주면 알 수 있다. 팩토리얼은 1부터 해당 수까지 전부 곱한 수이므로 $x!$ 에서 소인수로 존재하는 2의 개수는 $x$ 보다 작거나 같은 2의 배수들은 1개, 4의 배수들은 2개, 8의 배수들은 3개, 이런식으로 가지고 있다. 5 역시 마찬가지이며 몫과 나머지 연산을 통해서 2의 개수와 5의 개수를 전부 세줄 수 있다. 분자의 2의 개수와 5의 개수에서 분모의 2의 개수와 5의 개수를 빼줬을 때, 둘의 최솟값으로 10을 만들 수 있고 이것이 끝자리 0의 개수가 된다.

---

2. 코드

1. 풀이 [Java]

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 cnt2 = find(n, 2) - find(m, 2) - find(n - m, 2);
        int cnt5 = find(n, 5) - find(m, 5) - find(n - m, 5);
        System.out.println(Math.min(cnt2, cnt5));
    }

    static int find(int x, int div) {
        int cnt = 0;

        long tmp = div;
        while (x >= tmp) {
            cnt += (int) (x / tmp);
            tmp *= div;
        }

        return cnt;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

long long find(int x, int div) {
    long long cnt = 0;

    long long tmp = div;
    while (x >= tmp) {
        cnt += x / tmp;
        tmp *= div;
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    int cnt2 = find(n, 2) - find(m, 2) - find(n - m, 2);
    int cnt5 = find(n, 5) - find(m, 5) - find(n - m, 5);
    cout << min(cnt2, cnt5);
}

---