백준 2004 자바 - 조합 0의 개수

문제

---

 

 

문제해결

---

- 이 문제를 풀기 위해서는 공식을 알아야 한다

- n과m의 조합 = 2^(n - (n-m) - m) * 5^(n - (n-m) - m)

- getFivePower, getTwoPower 메서드로 n, n-m, m의 5로 나눌 수 있는 개수와 2로 나눌 수 있는 개수를 구한다

- 그렇다면 조합의 2의 승수와 5의 승수를 구할 수 있는데 매칭되는 개수만큼 0이 나온다

import java.util.Scanner;

public class B2004 {
    //num에서 5를 몇개까지 나눌 수 있는지 구하기
    public static int getFivePower(int num){
        int cnt = 0;
        while (num >= 5){
            cnt += num/5;
            num /= 5;
        }
        return cnt;
    }
    //num에서 2를 몇개까지 나눌 수 있는지 구하기
    public static int getTwoPower(int num){
        int cnt = 0;
        while (num >= 2){
            cnt += num/2;
            num /= 2;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //공식, n과m의 조합 = 2^(n - (n-m) - m) * 5^(n - (n-m) - m)
        int five = getFivePower(n) - getFivePower(n-m) - getFivePower(m);
        int two = getTwoPower(n) - getTwoPower(n-m) - getTwoPower(m);
        //2와 5가 매칭되는 수만큼 0이 생김
        System.out.println(Math.min(five, two));
    }
}

출처: https://st-lab.tistory.com/166

[백준] 2004번 : 조합 0의 개수 - JAVA [자바]