백준/1676 팩토리얼 0의 개수 // BigInteger , 0의개수 규칙

 

팩토리얼 0의 개수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

52448

25204

20824

47.857%

문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

---

풀이

//팩토리얼 문제 , 팩토리얼은 상당히 큰수를 만들게된다.
//여기서는 n이 최대 500이다. 500!는 상상도 못할 큰수일것이다. 팩토리얼 계산사이트에 500!를 입력해보니 너무큰숫자이다.
//이 숫자는 int이든 long이든 담을 수 없다.
//그럴때 사용하는것이 BigInteger이다. BigInteger는 문자열로 숫자를 받기때문에 , 숫자의 범위가 무한대이다.
//BigInteger를 이용해서 여러방법으로 팩토리얼을 계산해보자.

import java.io.*;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    //팩토리얼 문제 , 팩토리얼은 상당히 큰수를 만들게된다.
    //여기서는 n이 최대 500이다. 500!는 상상도 못할 큰수일것이다. 팩토리얼 계산사이트에 500!를 입력해보니 너무큰숫자이다.
    //이 숫자는 int이든 long이든 담을 수 없다.
    //그럴때 사용하는것이 BigInteger이다. BigInteger는 문자열로 숫자를 받기때문에 , 숫자의 범위가 무한대이다.
    //BigInteger를 이용해서 여러방법으로 팩토리얼을 계산해보자.

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        String result = facto(BigInteger.valueOf(n)).toString();
        int count =0;
        for (int i = result.length() - 1; i >= 0; i--) {
            if (result.charAt(i) == '0') {
                count++;
            }
            else{
                break;
            }
        }
        bw.write(count+"");

        bw.flush();
        bw.close();

    }

    public static BigInteger facto(BigInteger n) {
        //단순하게 반복문을 이용해서 팩토리얼값을 구한다.
        BigInteger result = new BigInteger("1");
        for (int i = 2; i <= n.intValue(); i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }


}

 

다른사람풀이

숫자뒤에 0이 붙는다는것은 2와 5를 곱할때 생성된다. 그래서 소인수분해해서 2와 5의 쌍 갯수를 세주면된다.

그리고 해당 수를 소인수분해했을때 2의 갯수는 항상 다른 인수들보다 많다.

그러므로 5의갯수를 세주면된다.  

+ 팩토리얼 표를 보고 규칙을 찾아서 풀이

 

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