[백준]2004번 조합0의 개수(java)

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

2004번: 조합 0의 개수

백준 2004번 조합 0의 개수 문제 링크입니다.

핵심

2와 5개가 짝을 이루어 곱해질 때마다 끝자리에 0이 1개 추가된다. 2와 5의 개수가 다르게 나올 수 있기 때문에, 둘 중 적게 나온 수만큼 0이 추가된다.

정답 코드

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());
        int countN =divide5(N) - (divide5(M) + divide5(N-M));
        int countM =divide2(N) - (divide2(M) + divide2(N-M));
        System.out.println(Math.min(countN,countM));
    }
    public static int divide5(int n){
        int cnt = 0;
        while(n >= 5){
            cnt += n / 5;
            n /= 5;
        }
        return  cnt;
    }
    public static int divide2(int n){
        int cnt = 0;
        while(n >= 2){
            cnt += n / 2;
            n /= 2;
        }
        return  cnt;
    }
}

해설

N과 M을 입력받는다. 쉽게 생각하면 예제 입력에 25와 12를 넣었는데,

이는 25! / 13!*12!이다.

즉 끝자리 0의 개수는 25! 의 끝자리 0의 개수 - 13! 과 12! 의 끝자리 0의 개수이다.

2와 5의 조합으로 0이 1개씩 추가된다.

따라서 5가 나온 횟수(5를 소인수로 가진 횟수)와 2가 나온 횟수(2를 소인수로 가진 횟수)중 더 적은 값을 선택한다.

 

 

 

 

 

개선점이나 오류가 있다면 댓글 부탁드립니다.