백준 2004 조합 0의 개수(Java)

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

2004번: 조합 0의 개수

---

 

해석 및 팁

 

---

 

이 문제를 풀려면 먼저 조합의 공식을 알아야 합니다. nCr = n! / r! * (n-r)! 이므로 분리해서 n! 에서 사용된 2 또는 5의 배수에서 (n-r)! 과 r! 의 2 또는 5의 배수를 빼주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int m = sc.nextInt();

    int result5 = cal5(n) - cal5(n - m) - cal5(m);
    int result2 = cal2(n) - cal2(n - m) - cal2(m);
    
    
    System.out.println(Math.min(result2, result5));
  }

  public static int cal5(int num) {
    int count = 0;
    while(num >= 5) {
      count += num / 5;
      num /= 5;
    }
    return count;
  }

  public static int cal2(int num) {
    int count = 0;
    while(num >= 2) {
      count += num / 2;
      num /= 2;
    }
    return count;
  }
   
}