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

1. 문제

2004번: 조합 0의 개수

---

2. 풀이

1.  N! / M!(N-M)!을 구해야하므로 2의 개수, 5의 개수를 각각 구한다.

2.  분모의 2, 5 개수는 플러스, 분자의 2, 5개수는 마이너스한다.

3.  2, 5 개수 중 더 적은 값을 출력한다. 10이 되려면 더 작은 개수에 맞춰야 하기 때문이다.

import java.io.*;
import java.util.*;

public class BOJ_2004_조합0의개수 {
   public static void main(String[] args) throws IOException {
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      long N = Integer.parseInt(st.nextToken());
      long M = Integer.parseInt(st.nextToken());

      int two = 0, five = 0;

      for(long i=2;i<=N;i*=2) {
         if(N!=0) two += N/i;
         if(M!=0 && i<=M) two -= M/i;
         if(N-M != 0 && i<=N-M) two -= (N-M)/i;
      }
      for(long i=5;i<=N;i*=5) {
         if(N!=0) five += N/i;
         if(M!=0 && i<=M) five -= M/i;
         if(N-M != 0 && i<=N-M) five -= (N-M)/i;
      }

      System.out.println(Math.min(two,five));
   }
}

---

3. 결과

전체 수의 2, 5개수를 각각 구하려니 메모리초과가 났다. 

이후에 본문과 같은 방식을 생각했는데, int의 범위로 충분하지 않아서 / by zero 런타임 에러가 났다. long으로 타입변환하니 해결되었다.