알고리즘 풀이/백준
[BOJ] 1676. 팩토리얼 0의 개수 - JAVA
2245
2023. 1. 27. 11:57
🔗 문제
https://www.acmicpc.net/problem/1676
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
🧩 풀이 및 코드
문제 유형 : 수학, 임의 정밀도 / 큰 수 연산
풀이
일단 뒤에 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();
}
}