[백준-2004] 조합 0의 개수 - Java

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

2004번: 조합 0의 개수

백준 2004번 조합 0의 개수 자바 풀이

난이도: 실버2

 

 

https://binsblog.tistory.com/entry/%EB%B0%B1%EC%A4%80-1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98-Java

[백준-1676] 팩토리얼 0의 개수 - Java

위의 문제 풀이방법과 비슷하다.

조합을 이용하였기 때문에

예를 들어 10C2인 경우

10!/(8!*2!)이다.

이런 경우 10!의 5의 개수는 2개, 2의 개수는 8개이다.

8!의 5의 개수는 1개, 2의 개수는 7개이다.

2!의 5의 개수는 0개, 2의 개수는 1개이다.

10C2를 계산할 경우

5의 개수는 2-1개 즉 1개,

2의 개수는 8-7-1개 즉 0개이다.

5의 개수와 2의 개수 중 최소값 만큼 0의 개수가 존재한다.

 

코드

import java.util.*;

public class back2004 {

    public static void main(String args[]){

        Scanner scanner=new Scanner(System.in);

        long num1=scanner.nextLong();

        long num2=scanner.nextLong();

        long count5=count_five(num1)-count_five(num1-num2)-count_five(num2);

        long count2=count_two(num1)-count_two(num1-num2)-count_two(num2);

        System.out.println(Math.min(count5, count2));

    }

    static long count_five(long num){

        int count=0;

        while(num>=5){

            count+=num/5;

            num/=5;

        }

        return count;

    }

    static long count_two(long num){

        int count=0;

        while(num>=2){

            count+=num/2;

            num/=2;

        }

        return count;

    }

}