[백준] 1676. 팩토리얼 0의 개수

---

문제

 

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

1676번: 팩토리얼 0의 개수

 

 일반적인 팩토리얼 구현 및 String 파싱 문제지만 N의 범위가 500까지다.

 수가 매우 커질 수 있기 때문에 자료형에 대한 고려가 필요하다.

 

 

---

전략

 

01. 일반적인 풀이

 N에 해당하는 팩토리얼을 구한 뒤 10으로 나눈 나머지가 0이 아닐 때까지 카운트하기

 

---

풀이

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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.parseInt(br.readLine());
        BigInteger facto = BigInteger.ONE;

        for (int i = 2; i < N + 1; i++) {
            facto = facto.multiply(BigInteger.valueOf(i));
        }

        int count = 0;

        while (facto.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            count++;
            facto = facto.divide(BigInteger.TEN);
        }

        System.out.println(count);
    }
}

 

 21!만 해도 long 자료형의 범위를 넘어버린다. (51,090,942,171,709,440,000 > 9,223,372,036,854,775,807) 즉 long 자료형으로 표현할 수 있는 팩토리얼의 범위는 20까지다.

 

 아무튼 N의 범위가 500까지이므로 일반적인 자료형으로는 표현할 수 없다. 따라서 더 큰 숫자를 표현하기 위해 java.math 라이브러리의 BigInteger를 사용한다. BigInteger는 다른 기본 자료형들처럼 Number 추상 클래스를 확장한다. BigInteger는 큰 숫자를 나타내기 위해 signum과 mag(magnitude)를 사용한다. signum은 숫자의 부호를 나타내기 위한 int자료형이며, mag는 큰 숫자들의 절대값을 나타내기 위한 int배열(int[])이다. 즉, BigInteger는 큰 숫자를 여러 개의 int배열로 쪼개서 저장하는 클래스라고 할 수 있다.

 

Python

 

import sys

N = int(sys.stdin.readline().rstrip())

facto = 1

for i in range(2, N + 1):
    facto *= i

count = 0

while facto % 10 == 0:
    count += 1
    facto //= 10

print(count)

 

 

 파이썬은 정수형 변수가 기본적으로 정수 배열 형태로 저장되므로 크기의 한계가 없다. 따라서 다음과 같이 간단한 코드로 풀 수 있다.

 

 

Javascript (Nodejs)

 

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().split("\n");

const N = Number.parseInt(input[0]);

let facto = 1n;

for (let i = 1; i < N + 1; i++) facto *= BigInt(i);

let count = 0;

while (facto % 10n == 0) {
  count++;
  facto /= 10n;
}

console.log(count);

 

 

 자바스크립트의 코드로는 다음과 같다. 자바스크립트도 또한 2^53승 이상의 수를 저장하기 위해서 BigInt를 도입했다. BigInt를 선언할 때는 BigInt(숫자) 또는 '숫자n'처럼 숫자 뒤에 n을 붙이면 된다. Java와 마찬가지로 자바스크립트의 BigInt도 정수 배열을 이용해 무한대의 숫자를 저장할 수 있다. 다만 일반적인 정수 타입인 Number와의 직접적인 연산은 불가능하므로 BigInt로 형변환해서 연산해야 한다.