[BOJ-2004][C++] 조합 0의 개수

문제

 ${n \choose m}$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 $n$, $m$ ($0≤m≤n≤2,000,000,000$ $n \ne 0$)이 들어온다.

 

 

출력

첫째 줄에 $n \choose m$의 끝자리 $0$의 개수를 출력한다.

 

예제 입력 1

25 12

 

예제 출력 1 

2

 

 

알고리즘 분류

• 수학
• 정수론

 

문제 출처

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

---

 

문제 해결 방법

• '팩토리얼 0의 개수' 문제와 비슷한 유형의 문제이다.
• 팩토리얼에서 0의 개수는 5의 지수 개수만 구하면 문제를 해결할 수 있었지만, 조합의 경우 다음과 같이 나누기 연산이 이루어지므로 10을 만드는 약수인 2와 5의 지수 개수를 모두 구해줘야 한다.

$${}_nC_{r} = \frac{n!}{r!(n-r)!}$$

• 위의 공식에서 `n!` 과 `r!`, 그리고 `(n - r)!` 의 2와 5의 지수 개수를 모두 구해준 후, `n!` 의 2와 5의 지수 개수에서 `r!` 과 `(n - r)!` 의 2와 5의 지수 개수의 합을 각각 빼주면 된다. 

// nCm = n! / m! x (n - m)!
numTwo = findNumOfDivisors(2, n) - (findNumOfDivisors(2, m) + findNumOfDivisors(2, n - m));    // 2의 지수의 개수 계산
numFive = findNumOfDivisors(5, n) - (findNumOfDivisors(5, m) + findNumOfDivisors(5, n - m));    // 5의 지수의 개수 계산

• 그리고 최종적으로 구해진 2의 지수 개수(numTwo)와 5의 지수 개수(numFive) 중, 작은 수를 출력시켜준다.

// 조합은 나누기 연산을 해야하고, 2 * 5 = 10 이기 때문에 둘 중에 작은 것을 출력시킨다.
result = (numTwo > numFive) ? numFive : numTwo;

 

• 팩토리얼에서 지수의 개수를 구하는 알고리즘은 다음과 같다.

방법 1

ull findNumOfDivisors(int div, ull n) { 
    int count = 0;

    while (n >= div) {
        count += n / div;
        n /= div;
    }
    
    return count;
}

 

방법 2

ull findNumOfDivisors(int div, ull n) {
    int count = 0;

    for (ull i = div; i <= n; i *= div) {
        count += (n / i);
    }

    return count;
}

 

코드

#include <iostream>
using namespace std;

using ull = unsigned long long;
ull n, m, numTwo, numFive, result;

// div의 지수의 개수 찾기
ull findNumOfDivisors(int div, ull n) { 
    int count = 0;

    while (n >= div) {
        count += n / div;
        n /= div;
    }
    
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // nCm = n! / m! x (n - m)!
    numTwo = findNumOfDivisors(2, n) - (findNumOfDivisors(2, m) + findNumOfDivisors(2, n - m));    // 2의 지수 개수 계산
    numFive = findNumOfDivisors(5, n) - (findNumOfDivisors(5, m) + findNumOfDivisors(5, n - m));    // 5의 지수 개수 계산
    
    // 조합은 나누기 연산을 해야하고, 2 * 5 = 10 이기 때문에 둘 중에 작은 것을 출력시킨다.
    result = (numTwo > numFive) ? numFive : numTwo;    
    
    cout << result << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론과 조합론]
• 실버II

팩토리얼(Factorial)에서 지수의 개수를 구하는 알고리즘

$$10! = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 2^{8} \times 3^{4} \times 5^{2} \times 7^{1} $$

$\Rightarrow$ 2의 지수는 8, 3의 지수는 4, 5의 지수는 2, 7의 지수는 1이다.

• 팩토리얼에서 지수의 개수를 구하는 알고리즘은 다음과 같다.

방법 1

int findNumOfDivisors1(int div, int n) { 
    int count = 0;

    while (n >= div) {
        count += n / div;
        n /= div;
    }
    
    return count;
}

 

방법 2

int findNumOfDivisors2(int div, int n) {
    int count = 0;

    for (ull i = div; i <= n; i *= div) {
        count += (n / i);
    }

    return count;
}