[백준] 1676 : 팩토리얼 개수 - JAVA

dev-jjun·2023년 1월 1일

boj 알고리즘

코딩테스트 준비

목록 보기

3/11

🔗 문제

BOJ 1676 : 팩토리얼 개수

난이도 - 실버 5

알고리즘 분류 - 수학, 임의 정밀도 / 큰 수 연산

💬 풀이

예시로 문제를 이해해보면, 10! = 3628800으로, 일의 자리부터 0이 아닌 수가 처음 등장할 때까지 수를 세보면 총 2개이다. 문제에서 숫자의 범위가 500까지로 주어져 있으므로 500!을 고려해보면 매우 큰 수이므로 자바에서 제공하는 BigInteger 클래스를 사용하는 방법도 떠올릴 수 있다.
하지만, 팩토리얼 내의 총 0의 개수가 아닌 뒤에서부터 0이 나오지 않을 때까지의 0만 카운팅하면 되므로 팩토리얼들의 규칙을 살펴보고 방법을 찾아보고자 하였다.
1! = 1 -> 0
2! = 2 -> 0
3! = 6 -> 0
4! = 24 -> 0
5! = 120 -> 1
6! = 720 -> 1
7! = 5040 -> 1
8! = 40320 -> 1
9! = 362880 -> 1
10! = 3628800 -> 2
11! = 39916800 -> 2
...
19! = 121645100408832000 -> 3
20! = 2432902008176640000 -> 4
1~20까지 팩토리얼을 구해보았을 때, 특정 숫자의 범위 내에서 0의 개수가 계속 동일하게 나오는 것을 볼 수 있다.
특정 숫자들의 공통점은 "5의 배수" 였고, 5라는 숫자를 반복문에서 적절히 활용하여 굳이 팩토리얼을 구하지 않고도 0을 셀 수 있다는 접근을 떠올릴 수 있다.
5 0 ~ 5 1 이전 -> 0
5 1 ~ 5 2 이전 -> 1
5 2 ~ 5 3 이전 -> 2
5 3 ~ 5 4 이전 -> 3

하지만 여기서
5 4 ~ 5 5 이전 -> 4 는 성립하나, 5 5 에서 갑자기 0의 개수가 6이 된다. 그 이유는 우리가 구하고자 하는 건 뒷 자리에 있는 0인데 이는 10이 몇 번 곱해졌는가를 의미한다. 즉, 0의 개수는 소인수분해 시 5가 몇 승인지로 판단 가능하지만 이때 2 5의 쌍이 동일하게 들어가야 한다는 것이다.
연속된 수를 곱할 때 2는 5보다 작아 2의 개수가 항상 더 많아지게 된다. 따라서 단순히 5로 나누며 카운팅해나가는 것만으로 간단하게 구현이 가능하다.

💻 코드

package Baekjoon;

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

public class _1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int cnt = 0;

        while (num >= 5) {
            cnt += num / 5;
            num /= 5;
        }

        System.out.println(cnt);
    }
}

📊 정리

BigInteger로 무작정 접근하며 정리한 'Java에서 큰 수 다루기' 내용이다.

BigInteger

자바에서는 변수의 정수 표현 범위를 넘어가는 경우를 고려하여 int, long의 원시 타입 대신 사용할 수 있는 BigInteger 클래스를 제공한다. 문제가 제시될 때 보통 최악의 경우도 고려해야 하므로 무한의 정수가 들어갈 가능성이 있다면 BigInteger를 사용하는 것이 좋다.

타입	범위	메모리 크기 (64bit 기준)	기본/참조형	저장된 위치
int	-2,147,483,648 ~ 2,147,483,647	4 Byte	기본형	Stack
long	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807	8 Byte	기본형	Stack
BigInteger	무한 (Infinity)	Minimum 70 Byte	참조형	Heap

BigInteger는 int, long, Integer, Long 과는 달리 문자열 형태로 숫자를 처리한다.

BigIntger는 표현하고자 하는 자리수에 비례하여 사용하는 메모리 크기가 늘어난다.

BigIntger의 메모리 크기는 최소 사이즈인 70 Byte에서 “7”과 같이 한 자리 수로만 사용할 때의 메모리 크기이다.

→ 따라서, 해당 클래스를 사용하는 것만으로 최소 메모리를 잡아먹는 크기가 크므로 무한이 아닌지 조건을 생각해보고 사용해야 한다.

❗ 사용법

BigInteger는 클래스 이므로, 사칙연산과 비교 등의 원시 타입에서의 숫자 연산을 모두 내부 메서드의 형태로 지원한다.

선언

import java.math.BigInteger;

BigInteger bigNum = new BigInteger("1000");

사칙연산

add(bigNum)	덧셈(+)
subract(bigNum)	뺄셈(-)
multiply(bigNum)	곱셈(*)
divide(bigNum)	나눗셈(/)
remainder(bigNum)	나머지(%)

*반드시 같은 BigInteger 간의 연산만 가능하다.

형 변환

intValue()	BigInteger → int
longValue()	BigInteger → long
floatValue()	BigInteger → float
doubleValue()	BigInteger → double
toString()	BigInteger → String
valueOf()	int → BigInteger

2개의 수 비교

compareTo 사용

작은 수를 큰 수랑 비교 50.comoareTo(100) → -1
2개의 수가 같을 때 → 0
큰 수를 작은 수랑 비교 → 1

참고 - https://lsmman.tistory.com/47

📍 어려웠거나 해결하지 못한 부분

처음에는 자바에서 기본으로 지원하는 큰 수 연산의 BigInteger를 사용하여 N 팩토리얼을 구하고, 뒤에서부터 10으로 나눈 나머지를 통해 자릿수를 비교하며 0을 카운트하는 원칙적인 방법을 사용하고자 했다. 하지만 BigInteger 자체가 다른 숫자형 타입과는 달리 문자열의 형태로 숫자를 처리하므로 입력값을 int로 받고 BigInteger로 처리하는 과정이 다소 복잡하였다.