[BOJ][2004] 조합 0의 개수

1. 문제 링크

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

2. 사용 알고리즘

수학

3. 풀이

끝자리가 0이 되기 위해서는 2와 5의 곱으로 이루어져야 한다.

따라서 2와 5 중 작은 것의 개수가 0의 개수가 된다.

nCm = n! / m!(n - m)!

n!에서 구한 2와 5의 개수는 더해주고, m!(n - m)!에서 구한 2와 5의 개수는 빼준다.

• n의 2의 개수 : n / 2^1 + n / 2^2 + n / 2^3 + …

• n의 5의 개수 : n / 5^1 + n / 5^2 + n / 5^3 + …

• m의 2의 개수 : m / 2^1 + m / 2^2 + m / 2^3 + …

• m의 5의 개수 : m / 5^1 + m / 5^2 + m / 5^3 + …

• n - m의 2의 개수 : (n - m) / 2^1 + (n - m) / 2^2 + (n - m) / 2^3 + …

• n - m의 5의 개수 : (n - m) / 5^1 + (n - m) / 5^2 + (n - m) / 5^3 + …

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/2004.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    long long twoCount = 0, fiveCount = 0;
    for (long long i = 2; i <= n; i *= 2) {
        twoCount += n / i;
    }
    for (long long i = 5; i <= n; i *= 5) {
        fiveCount += n / i;
    }
    for (long long i = 2; i <= m; i *= 2) {
        twoCount -= m / i;
    }
    for (long long i = 5; i <= m; i *= 5) {
        fiveCount -= m / i;
    }
    for (long long i = 2; i <= n - m; i *= 2) {
        twoCount -= (n - m) / i;
    }
    for (long long i = 5; i <= n - m; i *= 5) {
        fiveCount -= (n - m) / i;
    }
    cout << min(twoCount, fiveCount) << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/2004.java

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 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long twoCount = 0, fiveCount = 0;
        for (long i = 2; i <= n; i *= 2) {
            twoCount += n / i;
        }
        for (long i = 5; i <= n; i *= 5) {
            fiveCount += n / i;
        }
        for (long i = 2; i <= m; i *= 2) {
            twoCount -= m / i;
        }
        for (long i = 5; i <= m; i *= 5) {
            fiveCount -= m / i;
        }
        for (long i = 2; i <= n - m; i *= 2) {
            twoCount -= (n - m) / i;
        }
        for (long i = 5; i <= n - m; i *= 5) {
            fiveCount -= (n - m) / i;
        }
        System.out.println(Math.min(twoCount, fiveCount));
    }
}