[수학] 백준 - 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

-문제해설

처음에 팩토리얼 재귀함수로 하려니깐 값이 너무 커져서 틀렸다고 나왔다.

뭔가 굳이 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) )