[백준] 300 - 수학 1 : 조합 0의 개수 (!) (2004번 JAVA)

[백준] 300 - 수학 1 : 조합 0의 개수 (2004번 JAVA)

---

[개선 전 방법] (시간 초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Integer.parseInt(st.nextToken());
        long m = Integer.parseInt(st.nextToken());

        long a = count_five(n);
        long b = count_five(m);
        long c = count_five(n - m);

        long result_five = a - (b + c);

        a = count_two(n);
        b = count_two(m);
        c = count_two(n - m);

        long result_two = a - (b + c);
        
        bw.write(Math.min(result_five, result_two)+"\n");
        bw.flush();
        bw.close();
    }

    // n! 의 인수 5의 개수
    public static int count_five(long n){
        if (n < 5){return 0;}
        else{
            int count = 0; // 5의 개수
            for(long i=5; i<=n; i+=5){
                long val = i;
                while (val % 5 == 0){
                    count ++;
                    val = val / 5;
                }
            }
            return count;
        }
    }

    // n! 의 인수 5의 개수
    public static int count_two(long n){
        if (n < 2){return 0;}
        else{
            int count = 0; // 2의 개수
            for(long i=2; i<=n; i+=2){
                long val = i;
                while (val % 2 == 0){
                    count ++;
                    val = val / 2;
                }
            }
            return count;
        }
    }
}

---

[개선 후 방법]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Integer.parseInt(st.nextToken());
        long m = Integer.parseInt(st.nextToken());

        long count_five = five_power_num(n) - five_power_num(m) - five_power_num(n-m);
        long count_two = two_power_num(n) - two_power_num(m) - two_power_num(n-m);

        long result = Math.min(count_five, count_two);

        bw.write(result+"\n");
        
        bw.flush();
        bw.close();
    }

    // 5의 승수
    public static long five_power_num(long n){
        int count = 0;
        while(n >= 5){
            count += n/5;
            n /= 5;
        }
        return count;
    }

    // 2의 승수
    public static long two_power_num(long n){
        int count = 0;
        while(n >= 2){
            count += n/2;
            n /= 2;
        }
        return count;
    }
}