C++로 N!의 B진법 표현에서 후행 0의 개수 구하기

이 글에서는 주어진 수 N의 팩토리얼(N!)을 B진법으로 표현했을 때 끝에 연속해서 붙는 0(후행 0)의 개수를 구하는 문제를 다룹니다.

문제 예시

입력 : N = 7, 진법 = 2
출력 : 4
설명 : 7! = 5040 (10진수)이며, 2진수로는 1001110110000으로 표현되어 후행 0이 4개입니다.

입력 : N = 11, 진법 = 5
출력 : 2
설명 : 11! = 39916800 (10진수)이며, 5진수로는 40204314200으로 표현되어 후행 0이 2개입니다.

진법 변환 과정 복습

먼저 10진수를 다른 진법으로 변환하는 과정을 간단히 짚어보겠습니다. (5040)₁₀을 2진수로 바꾸는 예를 들어 보겠습니다.

방법은 간단합니다. 수를 2로 나눈 나머지를 기록하고, 몫을 다시 2로 나누는 과정을 더 이상 나눌 수 없을 때까지 반복합니다. 그다음 나머지들을 역순으로 읽으면 원하는 진법의 수가 됩니다.

이 과정에서 후행 0은 2로 나누었을 때 나머지가 0이 되는 횟수와 같습니다.

실제로 5040을 소인수분해하면 2⁴ × 3² × 5 × 7이 됩니다. 즉, 2는 5040을 나머지가 0이 되도록 정확히 4번 나눌 수 있으며, 이는 후행 0의 개수와 일치합니다. 이러한 원리를 이용하면 후행 0의 개수를 손쉽게 계산할 수 있습니다.

풀이 접근 방법

앞서 설명한 내용을 정리하면, N!을 B진법으로 표현할 때의 후행 0의 개수는 N!을 나누어떨어지게 하는 B의 최대 거듭제곱 지수와 같습니다. 예를 들어 진법이 B = 14라면, 14는 14진법에서 10으로 표현됩니다. 즉 (14)₁₀ = (10)₁₄입니다.

진법이 합성수인 경우에는 진법을 소인수분해한 뒤, 각 소인수가 N!에 포함된 지수를 르장드르 공식(Legendre's formula)으로 구하고, 소인수별 지수를 진법 내에서의 지수로 나눈 값 중 최솟값이 곧 답이 됩니다.

C++ 구현 코드

위 접근 방식을 구현한 C++ 코드는 다음과 같습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 진법(Base)을 소인수분해하여 소인수와 지수를 저장하는 함수
vector < pair < int, int >> primeFactorsofBase(int Base) {
    // 소인수와 소인수분해 시의 지수를 저장할 벡터 선언
    vector < pair < int, int >> factors;

    for (int i = 2; Base != 1; i++) {
        if (Base % i == 0) {
            int count = 0;
            while (Base % i == 0){
                Base = Base / i;
                count++;
            }
            factors.push_back (make_pair (i, count));
        }
    }
    return factors;
}


int main () {
    int N = 11, Base = 5;
    // N!을 나누어떨어지게 하는 진법(Base)의 최대 거듭제곱 찾기
    vector < pair < int, int >> prime_factors;
    // primeFactorsofBase() 함수로 소인수 구하기
    prime_factors = primeFactorsofBase(Base);

    int result = INT_MAX;
    for (int i = 0; i < prime_factors.size (); i++) {
        // 최소 거듭제곱 계산
        int count = 0;
        int r = prime_factors[i].first;
        while (r <= N){
            count += (N / r);
            r = r * prime_factors[i].first;
        }
        result = min (result, count / prime_factors[i].second);
    }
    // result에 저장된 후행 0의 개수 출력
    cout << "Number of trailing zeroes: " <<result;
    return 0;
}

실행 결과

Number of trailing zeroes: 2

코드 설명

소인수분해: primeFactorsofBase() 함수가 진법(Base)을 소인수분해하여 각 소인수와 그 지수를 vector<pair>에 저장합니다.
거듭제곱 계산: 각 소인수 p에 대해 르장드르 공식(N/p + N/p² + N/p³ + …)으로 N!에 포함된 p의 지수를 구합니다.
최솟값 선택: 소인수별 지수를 진법 내에서의 지수로 나눈 뒤, 그중 최솟값을 결과로 저장합니다.
결과 출력: 계산된 후행 0의 개수를 화면에 출력합니다.

시간 복잡도 측면에서도 진법 소인수분해에 O(√B), 각 소인수에 대한 지수 계산에 O(log N)이 소요되므로 매우 효율적으로 동작합니다.

마무리

이 글에서는 N!을 B진법으로 표현했을 때 후행 0의 개수를 구하는 문제를 르장드르 공식을 활용해 해결했습니다. C++ 구현 코드도 함께 살펴보았으며, 이 코드는 Java, C, Python 등 다른 언어로도 충분히 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.