[BaekJoon] 11687 팩토리얼 0의 개수

1.  문제 링크

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

2.  문제

요약

• 가장 끝의 0의 개수가 M인 N! 중 가장 작은 N을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000,000보다 작거나 같은 M이 주어집니다.
• 출력: 가장 끝의 0의 개수가 M인 N! 중 가장 작은 N을 출력하고 만약 없다면 -1을 출력합니다.

3.  소스코드

첫 번째 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getFacto(int num) {
		int five_num = 0;
		int result = 0;
		for(int i = 5; i <= num * 5; i += 5) {
			int temp = i;
			while(temp % 5 == 0) {
				five_num++;
				temp /= 5;
			}
			if(five_num == num) {
				result = i;
				break;
			}
			if(five_num > num) {
				result = -1;
				break;
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getFacto(num) + "\n");
		bw.flush();
		bw.close();
	}
}

두 번째 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getFacto(int num) {
		int start = 1;
		int end = 500000000;
		int result = -1;
		while(start < end) {
			int count = 0;
			int mid = (start + end) / 2;
			for(int i = 5; i <= mid; i *= 5) {
				count += mid / i;
			}
			if(count >= num) {
				if(count == num) {
					result = mid;
				}
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getFacto(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

첫 번째 풀이

• 끝에 0을 만드려면 10을 만들 필요가 있으므로 2와 5가 필요한데 2의 개수보다 5의 개수가 적으므로 5의 수가 끝의 0의 개수를 정합니다.
• 수가 5 늘어날 때마다 해당 수를 소인수분해했을 때 5의 개수가 늘어납니다.
• 그렇기 때문에 5부터 시작하여 (주어진 수 * 5)까지 수를 5씩 늘리면서 확인하여 5부터 현재 수까지 소인수분해했을 때의 5의 개수를 계속해서 더해가다 주어진 수와 같아졌을 때의 현재 수가 답이 됩니다.
• 25와 같이 소인수분해했을 때 5가 2개 이상 들어가있는 수도 있기 때문에 끝의 0의 개수가 주어진 수만큼 만들어질 수 없는 경우도 있습니다.
• 이러한 경우는 5씩 수를 늘리며 소인수분해했을 때의 5의 개수를 세다가 5의 개수가 주어진 수를 거치지 않고 넘어간 경우 주어진 수에 해당하는 답이 없다는 뜻이므로 -1이 답이 됩니다.

1. 5의 개수를 저장할 five_num이라는 변수를 생성하고 0으로 설정하며 답을 저장할 result라는 변수를 생성합니다.
2. 5부터 시작하여 (주어진 수 * 5)까지 5씩 수를 증가시키며 반복문을 돌면서 주어진 수만큼 5의 개수가 나왔을 때의 수를 찾습니다.
   1. 현재 수를 5로 나눴을 때의 나머지가 0일 때 동안 해당 수를 5로 나누고 5의 개수를 1씩 증가시킵니다.
   2. 1번의 반복문이 끝나고 5의 개수가 주어진 수와 같다면 현재 수가 답이 되므로 해당 수를 출력합니다.
   3. 1번의 반복문이 끝나고 5의 개수가 주어진 수를 넘는다면 주어진 수만큼 뒤의 0의 개수가 되는 경우가 존재하지 않으므로 -1을 출력합니다.
   4. 1번의 반복문이 끝나고 5의 개수가 주어진 수보다 작다면 다시 반복문을 돌면서 답을 찾습니다.

두 번째 풀이

• 이진 탐색을 이용하여 문제를 해결합니다.
• 위에서 설명하였듯이 소인수분해하였을 때의 5의 개수가 뒤의 0의 개수에 해당하므로 최소의 경우인 1을 start로, 최대인 경우인 문제에서 주어진 최대 수인 100,000,000에 5를 곱한 500,000,000을 end로 설정하고 범위를 반씩 좁혀가며 5부터 해당 수까지 소인수분해했을 때의 5의 개수를 찾아 주어진 수와 같을 때의 수를 구합니다.

1. 범위에서 시작 지점을 나타내는 start라는 변수를 만들고 최소의 경우인 1로 설정하고 끝 지점을 나타내는 end라는 변수를 만들고 최대의 경우인 500,000,000으로 설정합니다. 또한 답을 저장할 수 있는 result라는 변수를 생성합니다.
2. start 변수의 값이 end 변수의 값보다 작을 동안 반복문을 돌며 주어진 수와 5의 개수가 같아지는 순간을 찾습니다.
   1. 5의 개수를 나타내는 count라는 변수를 생성하고 0으로 설정합니다.
   2. 범위를 반씩 좁히기 위해 start와 end의 중간을 나타내는 mid라는 변수를 생성하고 start와 end의 중간값으로 설정합니다.
   3. 5부터 시작하여 mid까지 수를 5씩 곱하며 mid 변수값을 현재 수로 나눈 몫을 count에 더해갑니다. 이를 통해 5부터 mid까지 소인수분해했을 때의 5의 개수를 찾을 수 있습니다.
   4. 3번을 통해 구한 5의 개수가 주어진 수보다 크거나 같을 때,
      1) 5의 개수가 주어진 수와 같다면 해당 수가 답을 mid 변수값으로 변경합니다.
      2) 5의 개수가 주어진 수보다 크다면 수를 줄여야하므로 end 변수값을 mid 변수값으로 변경합니다.
   5. 3번을 통해 구한 5의 개수가 주어진 수보다 작다면, 수를 키워야하므로 start 변수값을 mid 변수값 + 1로 변경합니다.