[백준 JAVA] 2004 조합 0의 개수

이항계수 다 까먹었는데............

부랴부랴 개념정립을 위해 확통 인강 듣고 풀었다.

역시 뭐든 기초개념이 가장 중요하다.....

 

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

public class Main_2004이항계수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 끝자리 0은 10의 배수에서 오는 것으로, 소인수분해한 2와 5의 배수의 조합에 의해 정해진다.
        // 따라서 끝자리 0의 개수를 구하기 위해서는 n! 에서 2의 배수와 5의 배수의 개수를 구한뒤
        // m! 과 (n-m)! 에서의 2의 배수와 5의 배수를 빼준다.

        // 끝자리 0의 개수를 구하기 위해서는 2와 5의 배수의 개수를 따로 계산하고
        //그 중 작은 값을 끝자리 0의 개수로 결정한다.
        long count2 = countFactors(n, 2) - countFactors(m, 2) - countFactors(n - m, 2);
        long count5 = countFactors(n, 5) - countFactors(m, 5) - countFactors(n - m, 5);

        //5와 2의 승수 중에서 작은 값이 0의 끝자리이다.
        //0 (10의 배수) = (2x5)
        System.out.println(Math.min(count2, count5));
    }

    // n!에서 num의 배수의 개수를 구하는 함수
    private static long countFactors(int n, int num) {
        long count = 0;      // 배수의 개수를 저장할 변수
        long factor = num;   // 배수를 나타내는 변수, 초기값은 num

        // factor가 n 이하일 때까지 반복
        while (factor <= n) {
            count += n / factor;  // n을 factor로 나눈 몫을 count에 더한다
            if (factor > Long.MAX_VALUE / num) break;  // 오버플로우 방지를 위한 조건 
                                                          (오버플로우 = 값 초과)
            factor *= num;  // factor에 num을 곱해 다음 배수를 계산
        }

        return count;  // 계산된 배수의 개수 반환
    }
}

 

 

처음에 int 형 쓰다가 팩토리얼 쓸때도 int를 사용해서... 오버플로우 문제로 런타임 오류가 떴고

long을 써도 초과할 수가 있어서 초과할시 멈추도록 조건을 걸어줬다...

 

여러모로 개념이 가장 중요했던 문제

 

시간복잡도

factor가 n을 초과할 때 까지 루프를 실행하고 = 팩토리얼

문제에선 2와 5의 승수를 구해야 되기(10의 소인수) 때문에

시간 복잡도는 O(log_2(n) + log_5(n)) 이다.