[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]

 
www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

---

• 문제

 

 

 

정말 정말 쉬운 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이러한 문제는 직감상 어떤 규칙이 있겠구나라고 생각하면 더욱 좋다.

물론, 그러지 않고 입력값에 대하여 factorial 값을 구하고, 뒤의 0의 개수를 구하는 것도 방법일 수는 있다.

 

그러나 입력값이 최대 500, 즉 500! 을 구해야 하는지라 BigInteger 클래스를 써서 구해야 하거니와 값도 매우 크다.

 

참고로 500! 의 값은 다음과 같다.

500! = 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

 

 

이렇게 푸는 것보다 더 쉽게 풀 수 있는 방법이 있다.

 

조금만 고민해보자. 우리가 뒷자리가 0이 나오는 경우는 언제인가? 2와 5가 곱해져 있을 때다. 이 말은 거꾸로 말하자면 소인수분해를 해서 2와 5가 존재할 경우 뒷자리는 0으로 끝난다는 것이다.

 

예로들어 30은 2×3×5 로 2와 5가 포함되어있다.

 

조금 더 큰 수로 예를 들어볼까. 231400 의 경우 다음과 같다

2³×5²×13×89 로 2와 5가 포함된다.

 

이러한 소인수분해의 성질을 이용하면 매우 쉽게 풀 수 있다.

 

실제로 팩토리얼값을 나열해보면 다음과 같다.

 

보면 5의 배수마다 0의 카운트 값이 증가하는 것을 볼 수 있다.

근데 중요한 점이 하나 있다. 바로 입력값이 25일 때는 카운트 값이 1이 아닌 2가 증가한다.

 

 

왜 그럴까? 

 

생각해보자. 뒷자리가 0이 n개 있다는 의미는 2와 5가 n개씩 짝지어 존재한다는 것이다. (2×5 = 10 이므로)

앞서 예시를 들었던 두 수인 30과 231400의 소인수분해 값을 자세히 보자. 30은 2와 5가 1개씩 있어 짝지을 수 있는 개수가 1개다. 231400의 경우는 2는 3개, 5는 2개 있다. 2와 5를 짝지을 수 있는 개수는 고로 2개이며, 뒷 자리수 0의 개수와 같다.

 

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스레 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

 

즉, 기본적으로 5의 개수에 따라 값이 변화한다고 보면 된다. 그리고 5의 n승에 따라 카운트 값을 한 개 더 추가해주면 되지 않겠는가. 한마디로 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 해주어야 한다.

.

 

 

그러면 다음과 같이 아주 쉽게 짤 수 있다.

int count = 0;

while (num >= 5) {
	count += num / 5;
	num /= 5;
}

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

별반 다를 거 없이 입력 방법만 바꾸어 성능 차이를 보고자 한다. 알고리즘은 위의 것을 그대로 사용하겠다.

 

1 . Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int num = in.nextInt();
		int count = 0;

		while (num >= 5) {
			count += num / 5;
			num /= 5;
		}
		System.out.println(count);
	}

}

 

 

별달리 설명할 게 없는 코드다.

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

 

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 num = Integer.parseInt(br.readLine());
		int count = 0;

		while (num >= 5) {
			count += num / 5;
			num /= 5;
		}
		System.out.println(count);
	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23677504  -  방법 2 : BufferedReader

채점 번호 : 23677500  -  방법 1 : Scanner

 

 

 

---

• 정리

 

이 문제는 소인수 분해에 따른 규칙만 잘 찾으면 어렵지 않게 풀 수 있는 문제였다. 다만 저 표를 입력하는게 조금 힘들었달까..