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

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2

 

 

 

 

 

풀이 .

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

public class Main {
    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());

        // nCm = n! / (m! * (n-m)!)
        // m!, (n-m)!은 분모에 들어가기 때문에 역으로 뺴줘야 한다

        int cntOfTwo = 0, cntOfFive = 0;
        for(long i = 2; i <= n; i*=2) cntOfTwo += n / i;
        for(long i = 2; i <= m; i*=2) cntOfTwo -= m / i;
        for(long i = 2; i <= n-m; i*=2) cntOfTwo -= (n-m) / i;

        for(long i = 5; i <= n; i*=5) cntOfFive += n / i;
        for(long i = 5; i <= m; i*=5) cntOfFive -= m / i;
        for(long i = 5; i <= n-m; i*=5) cntOfFive -= (n-m) / i;

        int ans = Math.min(cntOfTwo, cntOfFive);
        System.out.println(ans);
    }
}

 

codeung.tistory.com/170 와 유사한 문제이다.

 

다만 이 문제에서는 5의 개수로 (2 * 5) 쌍의 개수를 퉁칠 수 없다.

 

nCm = n! / (m! * (n-m)!) 인데, n!을 m! * (n-m)! 으로 나눌 때 변수가 생길 수 있기 때문에 온전히 nCm 안에 있는 (2 * 5) 쌍의 개수를 전부 구해야 한다.

(분모에 위치한 m!, (n-m)! 에 대해서는 나온만큼 n!에서 나온 개수에서 빼주면 된다.)

 

주의할 점은 각 반복의 변수 i 를 int가 아닌 long으로 써야 한다는 것이다.

 

n, m의 상한은 20억으로 int의 범위 안에서 충분히 처리가 가능하긴 하지만.. 반복변수 i는 1씩 증가하는 것이 아니라 2배, 5배씩 증가하기 때문에 n과 int 범위 안에서 잘 있다가 갑자기 int 범위를 벗어나게 될 수 있기 때문이다.

 

실제로 int i 를 사용할 경우 0 divide exception이 발생하게 된다.