문제 풀이/[JAVA_자바] 백준

[JAVA / 자바] 백준 1676번 - 팩토리얼 0의 개수 (실버 4)

Seunghyun_KO 2022. 2. 21. 09:00
728x90
반응형

 문제 

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.


 입력 

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)


 출력 

첫째 줄에 구한 0의 개수를 출력한다.


 


 문제 접근 방법 

n!이라는 숫자의 일의 자리부터 처음으로 0이 아닌 수가 나오기 이전까지 총 0의 개수를 출력하는 문제이다.

예를 들면

3! = 6이므로 일의 자리부터 0이 아니므로 0을 출력

10! = 3268800이므로 일의 자리부터 십의 자리까지 0이 나오므로 2를 출력

이런식의 문제이다.

 

그렇다면 n이 입력되면 n!을 구해야 하는 것인가? 결론부터 말하면 아니다.

n!은 1~n의 곱으로 만들어진 수이다.

그렇다면 맨 뒷자리에 0이 오려면 인수로 10이 있다는 소리가 된다. 아직 이정도의 정보만으로는 n!을 구해야한다.

n!을 구하지 않고 n만으로 0의 개수를 세는 원리는 다음과 같다.

인수로 10이 오면 뒷자리에 0이 쌓인다고 했다. 그렇다면 10의 인수는 2와 5이다. 2와 5가 짝을 이루면 뒷자리에 0이 쌓이게 된다.

수를 인수분해할 때 5가 하나 더 곱해질 때 마다 2는 그보다 많이 곱해지게 되므로 인수에 5가 하나 더 곱해지는 타이밍을 알아내면 n!을 구하지 않아도 된다. (= 인수에 5가 하나 더 곱해지는 타이밍은 n이 5의 배수일 때)

n 5가 곱해진 개수
0~4 0
5~9 1
10~14 2
... ...
n*5 ~ (n+1)*5 - 1 n

따라서 정답은,

n이 입력되면 n을 5로 계속 나누어 0이 될 때까지 n을 몇 번 나눠줬는지 카운팅하여 그 값을 출력해주면 된다.


 JAVA 코드 풀이 

 코드 실행 결과 


 후기 

처음 문제를 보았을 때 무슨 문제인지 이해가 안돼서 한참을 이해하는데 시간을 쏟았던 것 같다. 문제를 이해한 후에는 문제를 푸는데 크게 어려움이 없었던 것 같다.


 문제 원본 

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

 

1676번: 팩토리얼 0의 개수

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 알고리즘 분류 

728x90
반응형