📙[Algo] 24.01.15 알고리즘

알고리즘 문제) BOJ 2004. 조합 0의 개수

2004번: 조합 0의 개수

문제 요약

• nCr 끝짜리 0의 개수 출력

시간 제한

• 2초

입력

• n, m
  
  • (0≤m≤n≤2*10^9, n≠0)

출력

• nCr 끝짜리 0의 개수 출력

접근법

• 0의 개수를 구한다…
  • 1000000000의 약수 생각해보기..
  • 10의 소인수는 2와 5이다.
  • 즉 끝자리 0이 되려면 nCr을 소인수했을때 2, 5가 최소 하나씩 존재해야함
  • 0의 갯수가 1개→최대 9개까지 등장할때
    • 2와 5의 개수가 각 1개에서 → 9개로 증가…!!!!
    • 즉, 이 쌍의 개수가 몇 개인지 찾아야함~!
    • 2, 2*2….. 으로 나누면서 2의 개수 구하기
    • 5, 5*5…. 으로 나누면서 5의 개수 구하기n! / r! 구하기..!!!
• 조합
  • nCr = n*(n-1)..(n-r+1) / r*(r-1)*…*1
    • 분자에서 2, 5 개수 구하기
      • n!에서 먼저 구하고
      • (n-r)!에서 구한다음에 위에서 구한 개수에서 빼준값
    • 분에서 2,5 개수 구하기
      • r!에서 개수 구한다.
    • 최종적으로 분자에서 구한 값 - 분모에서 구한 값 빼줌

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    static int cntTwo(long n){
        int answer = 0;

        long i = 2;

        while (i <= n) {
            answer += n / i;
            i *= 2;
        }

        return answer;
    }

    static int cntFive(long n){
        int answer = 0;

        long i = 5;

        while (i <= n) {
            answer += n / i;
            i *= 5;
        }

        return answer;
    }

//    static BigInteger factorial(int n){
//        if(n == 1) return new BigInteger(String.valueOf(1));
//        return new BigInteger(String.valueOf(factorial(n-1)))
//                .multiply(new BigInteger(String.valueOf(n)));
//    }
//
//    static BigInteger factorial2(int n, int r){
//        if(n == n-r+1) return new BigInteger(String.valueOf(n));
//        return new BigInteger(String.valueOf(factorial2(n-1, r)))
//                .multiply(new BigInteger(String.valueOf(n)));
//    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        // n!에서 2,5 개수 - ((n-r)!에서 2,5 개수 + r!에서 2,5개수)
        // => 2의개수끼리 빼고, 5의개수끼리 뺸다음 최솟값만큼... 이게 왜 아닐까,,,ㅠㅠㅠㅠ


        System.out.println( Math.min(cntTwo(n)-cntTwo(m)-cntTwo(n-m)
                , cntFive(n)-cntFive(m)-cntFive(n-m)));

        // 계산기가 잘못된 것이었다,,,,,,,,,

    }
}