Menu

Subscribe

[JAVA/백준] 수학 3: 팩토리얼 0의 개수

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. n!의 뒤에서부터 0이 아닌 숫자가 나올 때 까지 0의 갯수는 10의 배수가 몇 개인지 찾으면 된다.
  2. 10의 배수를 만들 수 있는 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

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

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. n까지의 2, 5가 몇 번 나오는지 확인한다
    • 5의 갯수는 n/5이다.
    • 그런데 25, 50, 75, 100..과 같이 5가 중복되는 것도 잇으므로 i를 5의 배수만큼 증가시키면서 n/i의 값을 더해준다.

👏 해결 완료!

참고