[백준/1676번/java] - 팩토리얼 0의 개수
처음 문제를 읽고 나서 문제를 이해하는데에 조금 시간이 걸렸다! 저게 뭔소린지..
근데 10! 을 해보면 362800 이 나오는데 맨 오른쪽에 0이 두개! 그래서 2가 출력된다고 이해해보자.
만약 문제가 무슨 소리인지 모르겠어서 찾아봤다면, 아래를 읽어보기 보다는 다시 문제를 살펴보고 오는것이 좋을 것 같다.
첫번째 접근 방식은 다음과 같았다.
/**
* 1. N 입력받음
* 2. for 문으로 팩토리얼 계산 / 재귀 함수를 이용해서 만들기
* 3. 10으로 나눈 나머지가 0 이 아닐 때 까지 나누고 갯수 세기
*/
왜 10으로 나누게 되었냐면 362800 은 100의 배수이므로 10으로 두번 나눌 수 있고, 그 이후에는 10으로 나누어 떨어지지 않는다는걸 확인할 수 있다. 그래서 while 문을 이용해 10으로 몇번 나눌 수 있는지 확인해야겠다고 생각했다.
그래서 나온 코드가 아래의 코드이다.
import java.util.Scanner;
public class boj_1676 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int result = 1;
/**
* for 문으로 팩토리얼 계산하는 법
*/
for(int i = N; i > 0; i--){
result *= i;
}
int cnt = 0;
while(result % 10 == 0){
result /= 10;
cnt++;
}
System.out.println(cnt);
}
/**
* 재귀 함수로 계산하는 법
*/
static int factorial(int n){
if(n ==1)
return 1;
return n * factorial(n-1);
}
}
재귀 함수를 이용하는 방법과 그냥 for 문을 이용해 구하는 방법 두가지를 모두 구현해보았고, 정답이 문제없이 나와서 당당하게 제출을 했다..! 결과는 시간초과
첫번째 수정사항. N 으로 들어올 수 있는 최대 수는 500이므로 int 로 담아낼 수 없다. 그래서 BigInteger 을 사용해야한다.
두번째 수정사항. 팩토리얼 계산을 전부하고나서 다시 또 10으로 나누는 방법은 시간이 너무 오래걸린다. 다른 방법을 생각하는 것이 필요하다. 소인수분해를 생각해보기로 했다.
10을 인수로 가지고 있다는 말은 소인수분해를 했을 때 2 x 5 가 들어있다는 말이다.
0이 N 개 있다는 말은 2 x 5 의 쌍이 N 개 있다는 말과 동일하다.
여기서 중요한 점. 2는 5보다 작은 수이기 때문에 당연히 숫자가 커지면서 2가 5보다 많이 등장하게 되어있다. 그런데 10을 만들려면 2와 5의 갯수가 같이 증가해야하고, 만약 2가 10개 5가 2개라면 10은 2개만 생길 수 있으므로 갯수를 결정짓는 것은 5이다.
그래서 5를 기준으로 나누고, 갯수를 카운트해보자.
for 문이 하나씩 증가하는 팩토리얼이라고 생각해보자. for 문을 살펴보면 1부터 N 까지 숫자를 하나씩 증가시키면서 5의 배수인지 확인하는 과정이다. 5의 배수라면 5가 몇번 곱해졌는지 확인하는 부분이라고 보면 된다.
예를 들어보면, 10!은 1x2x3x4x5x6x7x8x9x10 인데 for 문이 저 숫자들을 의미하는것이고 만약에 저 숫자가 5로 나누어지는 수라면 그 수 안에 5가 몇번 곱해져있나 확인하는 것이 while 문의 역할이라고 보면 된다. 전체 코드는 다음과 같다.
import java.util.Scanner;
public class boj_1676 {
/**
* 1. N 입력받음
* 2. 5로 나누고 그 갯수 세기
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int cnt = 0;
for(int i = 1; i<= N; i++){
int num = i;
while(num % 5 == 0){
num /= 5;
cnt++;
}
}
System.out.println(cnt);
}
}
끝!