[수학] 백준 - 팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
-문제해설
처음에 팩토리얼 재귀함수로 하려니깐 값이 너무 커져서 틀렸다고 나왔다.
뭔가 굳이 n!을 다 구하지 않고 0의 개수만 알 수 있는 방법이 없나 생각하다가
그냥 노가다로 인터넷에 팩토리얼 계산기를 이용해서 규칙이 있는 지 확인했는데
신기하게도 규칙이 있었다. ㅎ
1~4 : 0
5~9 : 1
10~14 : 2
15~19 : 3
20~24 : 4
ㅡㅡㅡㅡㅡ25의 배수일 때는 + 2
25~29 : 6
.
.
.
45~49 : 10
ㅡㅡㅡㅡㅡ
50~54 : 12
.
.
.
70~74 : 16
ㅡㅡㅡㅡㅡ
75~79 : 18
.
.
.
120~124 : 28
ㅡㅡㅡㅡㅡ 125의 배수일 때는 +3
125~129 : 31
즉 이를 식으로 나타내면
( n / 5*5^0 ) + ( n / 5*5^1 ) + ( n / 5*5^2 ) + ....
이렇게 된다.
근데 문제에서 n이 500이하라고 했으므로 n / 5*5^3 까지는 필요없다.
그래서 아래 소스코드 처럼 간단하게 나타낼 수 있다.
이외에도 n이 2와 5로 나눠지는 개수로 0의 개수를 구할 수 있다.
예를 들어 n이 10라고 했을 때 반복문 i의 변수를 2부터 10까지 순회시킨다.
각 순회할 때마다 i를 2로 먼저 나눌 수 있을 만큼 나누고
그 다음 5로 나눌 수 있을 만큼 나눈다.
이때 2로 나눈 횟수를 a, 5로 나눈 횟수를 b에 누적시킨다.
int a = 0;
int b = 0;
for( int i=2; i<=n; i++ ) {
int num = i;
while( num % 2 == 0 ) {
num /= 2;
a++;
}
while( num % 5 == 0 ) {
num /= 5;
b++;
}
}
int answer = Math.min( a, b );
System.out.println( answer );
이는 파이썬 코드로 나타내봤다.
-자바
package math;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ1676 {
static int n;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt( br.readLine() );
System.out.println( (n/5)+(n/25)+(n/125) );
}
}
-파이썬( 파이썬 한 줄 개꿀 ㅎ )
n = int( input() ); print( (n//5)+(n//25)+(n//125) )
-파이썬( 2와 5의 나눗셈으로 풀기 )
n = int( input() );
a = 0; b = 0
for i in range( 2, n+1 ):
num = i
while num%2==0:
num /= 2
a += 1
while num%5==0:
num /= 5
b += 1
print( min(a, b) )