백준 1676번 팩토리얼 0의 개수 [JAVA]

문제 출처: https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

Sol1) BigInteger 클래스를 이용해 팩토리얼의 값을 구하고 0을 세는 방법

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        BigInteger facto = new BigInteger("1");

        int cnt = 0;

        while(num > 0){
            facto = facto.multiply(BigInteger.valueOf(num));
            num--;
        }

        while(true){
            if(facto.mod(BigInteger.TEN).equals(BigInteger.valueOf(0))) {
                cnt++;
                facto = facto.divide(BigInteger.TEN);
            }
            else
                break;
        }
        System.out.println(cnt);
    }
}

 

Sol2) 5의 개수를 세는 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int inputNum = Integer.parseInt(br.readLine());
		int cnt = 0;
 
		while (inputNum >= 5) {
			cnt += inputNum / 5;
			inputNum /= 5;
		}
		System.out.println(cnt);
	}
}

 

• 풀이 방향

풀이 방향은  두가질 잡을 수 있을 것 같다.

 

1. 단순하게 팩토리얼의 값을 구해서 0의 개수를 세는 방법

2. 팩토리얼의 자릿수에 0이 등장시킬 수 있는 가장 작은 수인 10이 몇번 곱해져 있는지 세는 방법

 

1번의 경우 BigInteger 클래스를 사용하면 쉽게 해결된다.

2번의 경우, 10은 1과 자기자신을 제외하면 2와 5를 약수로 가지고 있으므로 팩토리얼 값의 2와 5의 개수를 세면 되겠다. 그런데 관찰을 해보면 2와 5가 함께 존재할 때 항상 5의 개수보다 2의 개수가 많게 되므로 5의 개수만 세주면 되겠다.

 

• 풀이

1번 풀이의 경우 팩토리얼의 값을 구한 뒤 % 10 을 해주며 일의 자리부터 0의 개수가 몇개인지 세준다.

2번 풀이의 경우 팩토리얼이 5의 배수가 될 때마다 값을 올려주면 된다. 

 

예를 들면, 5!의 경우 1*2*3*4*5 로 5가 하나 있으므로 팩토리얼의 0의 개수 또한 하나일 것이다.

6! 또한 1*2*3*4*5*6 으로 5의 개수에는 변화가 없으니 한개다. 7!, 8!, 9!도 마찬가지이다.

10!이 되면 1*2*3*4*5*6*7*8*9*10 이 되는데, 10은 2*5 이므로 5의 배수이다. 즉, 10!부터는 5가 하나 더 추가된다.

11!, 12!, 13!, 14! 까지도 5의 배수가 곱해지지 않으므로 10!과 5의 개수는 2개로 똑같다.

이 식을 일반화하면, inputNum / 5 가 곧 inputNum!이 가지고 있는 5의 개수가 되는 것이다.

 

그런데, 여기서 주의점이 있다. 바로 5의 거듭제곱의 경우이다. 일반적인 5의 배수의 경우, 5를 하나만 포함하고 있기때문에 팩토리얼의 0의 개수를 1만 늘려주면 되지만, 5의 거듭제곱의 경우 5를 여러개 포함하고 있으므로 하나만 올려주어서는 안된다. 

예를 들면, 25의 경우 24!의 값에 5*5가 곱해지는 것이 되므로 카운트를 한개가 아니라 두개 올려주어야 한다. 

 

이를 고려하기 위해 누적합을 도입해야 한다.

25는 5의 배수지만, 5보다 5가 하나 더 많으므로 5의 배수를 센 값에 누적해서 25의 배수를 센 값을 더해줘야 한다. 그렇게 하면 5의 개수 + 25가 가져오는 추가적인 5의 개수를 모두 고려할 수 있게 된다. 

 

125의 경우도 마찬가지이다.  125는 25의 배수지만, 25보다 5가 하나 더 많으므로 5의 개수 + 25가 가져오는 추가적인 5의 개수에 누적해서 125가 가져오는 추가적인 5의 개수를 구해주어야 한다는 얘기이다.

 

이제 본격적인 풀이에 들어가보자.

어떤 수 x가 주어지면 x!이 약수로 가지고 있는 5의 개수를 세기 위해 x / 5를 해준다. 이런 식으로 셀 수 이유는 간단하다.

만일 x 가 15면, 이는 5의 세번째 배수이다. 15!에는 5의  첫번째 배수인 5와 두번째 배수인 10이 포함돼 있기 때문에 5의 몇번째 배수인지 세는 것만으로도 우리는 x!안에 포함된 5의 개수를 셀 수 있다.

 

이제 계속해서 x /= 5, x / 5 를 반복해 x!이 약수로 가지고 있는 25, 125와 같은 5의 거듭제곱의 배수의 개수를 세준다. 

 

해당 수의 25의 배수의 개수를 세는 것은 곧 25가 가지고 오는 추가적인 5의 개수를 센다는 이야기이고, 125의 배수의 개수를 세는 것은  곧 125가 가지고 오는 추가적인 5의 개수를 센다는 이야기이다. 이를 그림으로 표현하면 다음과 같다.

빨간색 - 5의 개수, 초록색 - 25가 가지고 오는 추가적인 5의 개수, 파란색 - 125가 가지고 오는 추가적인 5의 개수

 

• 문제에 대한 사견

문제 자체는 어렵지 않았지만, 나의 풀이를 정당화하기 위한 설명은 조금 까다로운 문제였다.