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

[Silver V] 팩토리얼 0의 개수 - 1676

문제 링크

성능 요약

메모리: 11488 KB, 시간: 76 ms

분류

수학

제출 일자

2023년 12월 13일 15:56:31

문제 설명

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

입력

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

출력

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

 

 

풀이 방법(1)

1. 일단 n의 최대값은 500임으로 그냥 숫자로는 풀 수 없고 BigInteger로 풀 수 있음

2. BigInteger을 통해서 주어진 n값까지 팩토리얼을 구해준다.

3. 뒤에서부터 확인하여 0의 개수를 센 후 출력해주면 된다.

package com.pratice;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        // 시작 값 "1"로 BigInteger생성
        BigInteger prev = new BigInteger("1");
        for (int i = 2; i <= n; i++) {
            // 2부터 시작하여 n까지 BigInteger을 곱해줌.
            BigInteger cur = new BigInteger(String.valueOf(i));
            prev = prev.multiply(cur);
        }
        // 팩토리얼 값 result에 저장
        String result = prev.toString();
        // 뒤에서부터 0의 개수를 세어준다.
        int count = 0;
        for(int i = result.length()-1; i >= 0 ;i--){
            if(result.charAt(i) != '0'){
                break;
            }else{
                count++;
            }
        }
        System.out.println(count);
    }
}

 

풀이 방법(2)

1. 0이 나오는 경우가 늘어나는 수를 본다면

5! = 120

10! = 3628800

15! = 1307674368000

20! = 2432902008176640000

25! = 15511210043330985984000000

즉 2 x 5의 쌍이 있을 때 마다 0이 증가함

2. 그런데 2가 나타나는 개수는 5보다 현저히 많음

3. 그러므로 5가 나타나는 개수만 세어주면 정답

4. 5가 나타날 수 있는 경우는 5의 제곱수 혹은 5의 배수이다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 주어진 값 중 2, 5가 몇번 들어가있는지를 확인해야함
        // 2는 5보다 훨씬 많이 들어가기때문에 0의 개수는 5가 결정한다. -> 즉 5의 개수만 세어주면 됨
        // 5! -> 5가 한번
        // 10! -> 5, 10(5 x 2)
        // 15! -> 5, 10(5 x 2), 15(3 x 5)
        // 20! -> 5, 10(5 x 2), 15(3 x 5), 20(4 x 5)
        // 25! -> 5, 10(5 x 2), 15(3 x 5), 20(4 x 5), 25(5 x 5)
        int answer = 0;
        for(int i = 1; i <= n; i++){
            // 5로 나누어 떨어진다면
            if( i % 5 == 0){
                // num에 i를 저장해줌
                int num = i;
                // 5의 제곱수도 있을 수 있으므로 확인하여 더해준다.
                while(num % 5 == 0){
                    num /= 5;
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
}