[백준] no1676: 팩토리얼 0의 개수

문제

1. 주어진 숫자 N의 N!를 구한다.

2. N! 결과값에서 1의자리부터 시작해서, 처음으로 0이 아닌 수가 나올 때까지 0의 갯수를 세아려 출력한다.

 

문제 링크 : https://www.acmicpc.net/problem/1676

 

---

원리

1. 0!은 1*0!이기 때문에 1이다.

2. 타입을 조심하자. 500!은 Long으로 표현하기엔 너무나도 큰 수이다.

---

풀이방법

1. 0! = 1이므로, 결과값은 0으로초기화 하면 된다.

 

2. 팩토리얼 계산에서 BigInteger타입을 사용하자.

* BigInteger는 사실상 무한대에 가까운 숫자를 표현할 수 있다.

* 만약 단순히 int나 Long을 사용하면 문제에 주어진 범위 500!은 0이된다.

* 만약 int나 Long을 사용하고 moduler를 하더라도, 실제 팩토리얼 결과값에서 표현된 0의 갯수를 구할 수 없다.

 

---

나의 코드

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

public class no1676 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Long N = Long.valueOf(br.readLine());
        String fact = String.valueOf(factorial(N));
        // 0! = 1 * 0! = 1이다.
        int result = 0;
        for (int i = fact.length() - 1; i >= 0; i--) {
            if (fact.charAt(i) != '0') break;
            result++;
        }
        System.out.println(result);
    }

    /**
     * 완벽한 팩토리얼 공식
     * @param n 입력인 n은 최대값이 500이기때문에 int나 Long도 가능하다
     * @return BigInteger는 무한대에 가까운 숫자를 표현할 수 있다
     */
    public static BigInteger factorial(Long n) {
        BigInteger p = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            p = p.multiply(BigInteger.valueOf(i));
        }
        return p;
    }
}

---

팩토리얼 공식

/**
 * 완벽한 팩토리얼 공식
 * @return BigInteger는 무한대에 가까운 숫자를 표현할 수 있다
 */
public static BigInteger factorial(Long n) {
    BigInteger p = BigInteger.ONE;
    for (int i = 1; i <= n; i++) {
        p = p.multiply(BigInteger.valueOf(i));
    }
    return p;
}