(17) [C++, Java] 백준 No.2004 : 조합 0의 개수

문제

풀이

자세한 풀이 : 

 

# C++
- 인수분해한 결과에서 2의 개수를 구할때, 바로 이전 문제에서 5의 개수를 구할 때 사용한 방법을 똑같이 사용하면 된다.
- 단, i*=2, i*=5의 결과가 int형을 넘을 수 있으므로 long long 형을 사용한다.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int n, m;       //  1 <= m <= n <= 2,000,000,000 

    cin >> n >> m;  // nCm = n! / m!(n-m)!

    int two = 0;
    for (long long i = 2; i <= n; i*=2)
        two = two + (n/i);

    for (long long i = 2; i <= m; i*=2)
        two = two - (m/i);

    for (long long i = 2; i <= (n-m); i*=2)
        two = two - ((n-m)/i);

    int five = 0;
    for (long long i = 5; i <= n; i*=5)
        five = five + (n/i);

    for (long long i = 5; i <= m; i*=5)
        five = five - (m/i);

    for (long long i = 5; i <= (n-m); i*=5)
        five = five - ((n-m)/i);

    cout << min(two, five) << "\n";
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long two = 0, five = 0;
        for (long i=2; i<=n; i*=2) {
            two += n/i;
        }
        for (long i=2; i<=n-m; i*=2) {
            two -= (n-m)/i;
        }
        for (long i=2; i<=m; i*=2) {
            two -= m/i;
        }
        for (long i=5; i<=n; i*=5) {
            five += n/i;
        }
        for (long i=5; i<=n-m; i*=5) {
            five -= (n-m)/i;
        }
        for (long i=5; i<=m; i*=5) {
            five -= m/i;
        }
        System.out.println(Math.min(two,five));
    }
}