Menu

Subscribe

[JAVA/백준] 수학 3: 조합 0의 개수

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. nCm=n!/m!(n-m)!이므로 분자 값의 2, 5의 갯수-분모 2, 5의 갯수를 구해서 2와 5 중 작은 값을 출력한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.Scanner;
/**
 * @author HEESOO
 *
 */
public class Main {
	public static int count(long n, long d) {
		int answer=0;
		for(long i=d;i<=n;i*=d) {
			answer+=n/i;
		}
		return answer;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		long n=input.nextLong();
		long m=input.nextLong();
		
		long five=count(n, 5);
		long two=count(n, 2);
		
		five-=count(m, 5);
		two-=count(m, 2);
		
		five-=count(n-m, 5);
		two-=count(n-m, 2);
		
		System.out.println(Math.min(two, five));
	}
}

3. 결과

실행결과 🤟 성공 🤟 첫 번째 실패는 마지막 two계산에서 -를 빼먹었기 때문이다.

4. 설명

  1. 분모, 분자 별 2, 5가 몇 번 나오는지 확인한다
    • 끝자리 0의 갯수를 구해야 하므로 10의 배수가 몇 개인지 체크하면 된다.
    • 10의 배수는 2, 5로 만들어지므로 두 갯수 중 최솟값을 취하면 된다.
    • 분모 갯수-분자 갯수한 2, 5 값 중 최솟값을 리턴한다.

👏 해결 완료!

참고

출처: https://suri78.tistory.com/45 [공부노트] https://suri78.tistory.com/45