[BOJ]2004번: 조합 0의 개수(java, c++)

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

2004번: 조합 0의 개수

 

 

방법 1: while문 하나 안에서 조건을 나누고 한번에 계산하기 (java)

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        try {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
            long fiveCount = 0;
            long twoCount = 0;
            long k = 5;
            long l = 2;
            while (n / l > 0) {
                if (k <= n) {
                    fiveCount += n / k - (n - m) / k - m / k;
                    k *= 5;
                }
                twoCount += n / l - (n - m) / l - m / l;
                l *= 2;
            }
            long result = (fiveCount > twoCount) ? twoCount : fiveCount;
            System.out.println(result);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
 

 

 

방법 2: 여러번의 for문을 돌려 각각 계산하기 (java)

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        try {
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
 
            long fiveCount = 0;
            long twoCount = 0;
            
            // nCm에서 5 개수 = n! 5개수 - (n-m)! 5개수 - m! 5개수
            long k = 5;
            while (n / k > 0) {
                fiveCount += n / k;
                k *= 5;
            }
            
            k = 5;
            while ((n - m) / k > 0) {
                fiveCount -= (n - m) / k;
                k *= 5;
            }
            
            k = 5;
            while (m / k > 0) {
                fiveCount -= m / k;
                k *= 5;
            }
 
            // nCm에서 2 개수 = n! 2개수 - (n-m)! 2개수 - m! 2개수
            long l = 2;
            while (n / l > 0) {
                twoCount += n / l;
                l *= 2;
            }
            
            l = 2;
            while ((n - m) / l > 0) {
                twoCount -= (n - m) / l;
                l *= 2;
            }
            
            l = 2;
            while (m / l > 0) {
                twoCount -= m / l;
                l *= 2;
            }
            
 
            long result = (fiveCount > twoCount) ? twoCount : fiveCount;
            System.out.println(result);
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
 

 

 

방법 3 : 따로 함수로 빼주기 (c++)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
// num! 팩토리얼에서 div 개수 구하기
int get_factorial_div_cnt(int num, int div)
{
    int cnt = 0;
    for (long long i = div; num / i >= 1; i *= div)
    {
        cnt += num / i;
    }
    return cnt;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    // nCm 조합에서는 인수 2와 5 중 어떤 것의 개수가 더 큰지 알 수 없다.
    // 각각 계산 후 더 적은 것의 개수가 0의 개수와 같다. 
    int cnt_2 = get_factorial_div_cnt(n, 2) - get_factorial_div_cnt(m, 2) - get_factorial_div_cnt(n - m, 2);
    int cnt_5 = get_factorial_div_cnt(n, 5) - get_factorial_div_cnt(m, 5) - get_factorial_div_cnt(n - m, 5);
 
    cout << min(cnt_2, cnt_5);
 
    return 0;
}

 

 

방법 1: while문 하나 안에서 조건을 나누고 한번에 계산하기

          5의 배수보다 2의 배수가 더 반복문을 많이 돌 것이므로, 반복문의 기준은 2의 배수로 잡았다. 

방법 2: 여러번의 for문을 돌려 각각 계산하기

방법 3: 함수로 따로 빼서 코드 재활용성 높이기

 

방법 2가 메모리를 살짝 덜 먹었지만 시간은 똑같았다.

하지만 코드가 더 간결하므로 나는 방법1이 더 마음에 든다.

20200418 따로 함수로 빼주는 방법3이 제일 가독성이 좋다!

 

 

 

조합 Combination

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

 

 

TIP1

조합에서 0의 개수를 구할때에는 팩토리얼에서 0의 개수를 구할때보다 좀 더 주의해야 한다.

팩토리얼에서는 5의 개수만 구하면 되었지만, 

조합에서는 나누어지는 수가 있으므로 min(2의 개수, 5의 개수)가 0의 개수가 된다. 

 

 

 

TIP2

n, m이 20억 이하의 숫자라고 해서 수들을 int형으로 선언하면 안된다.

 

    while (n / l > 0) {

         l *= 2;

    }

 

마지막에 l * 2를 해서 while문을 벗어날 때 l에서 오버플로가 발생할 수 있기 때문이다.

항상 오버플로 가능성을 잘 살펴보고 int형, long형을 선택하자

c++의 경우 long long형을 선택하자. long형으로는 l * 5가 오버플로 될 수 있다.