[BOJ] 1676. 팩토리얼 0의 개수 - JAVA

🔗 문제

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

1676번: 팩토리얼 0의 개수

 

🧩 풀이 및 코드

문제 유형 : 수학, 임의 정밀도 / 큰 수 연산

 

풀이

일단 뒤에 0이 붙는다는 건 2 x 5 가 곱해져 있을 떄다. 즉, 소인수분해를 해서 2 x 5 쌍의 갯수만큼 뒤에 0이 붙는다는 의미이다.

예를 들어, 30은 30 = 2×3×5 로 2와 5의 쌍이 1 개 이므로 0이 1개 붙는다.

조금 더 큰 수로 예를 들면 231400 의 경우 

2와 5의 쌍이 2개 이므로 0이 2개가 붙는다. (231400)

팩토리얼과 소인수분해를 쭉 나열해 보면 다음과 같다. 

보면 N!의 N 이 5의 배수일 때마다 1씩 증가하는 것을 볼 수 있다. (항상 2의 갯수보다 5의 갯수가 적기 때문에, 2 x 5 의 쌍의 갯수를 셀 때 5의 갯수를 세면 된다.) 대신, 25! 인 경우를 보면 0이 2개 증가했다. 25는 5의 2 승이기 때문에 2개 증가했다.

 

즉, 기본적으로 N이 5의 배수라면 0의 갯수가 1씩 증가하는데, 5의 n승이라면 추가로 더 증가한다.

한마디로, 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 해주어야 한다.

 

따라서 코드로 나타내면

int count = 0;
 
while (num >= 5) {
	count += num / 5;
	num /= 5;
}

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_1676_팩토리얼0의개수 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1676.txt"));
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int cnt = 0;
		while(N>=5) {
			cnt += N/5;
			N/=5;
		}
		
		System.out.println(cnt);
		sc.close();
	}

}

 

---

Reference

https://st-lab.tistory.com/165