이 글에서는 주어진 수 N의 팩토리얼(N!)을 16진수로 표현했을 때 뒤에 붙는 0(후행 0)의 개수를 구하는 문제를 다룹니다.
입력 : N = 7 출력 : 1 설명 : fact(7) = 5040 (10진수), 16진수로는 13B0이며 후행 0이 1개입니다. 입력 : N = 11 출력 : 2 설명 : fact(11) = 39916800 (10진수), 16진수로는 2611500이며 후행 0이 2개입니다.
진법 변환 과정 복습
먼저 10진수를 다른 진법으로 변환하는 과정을 간단히 복습해 보겠습니다. (5040)₁₀을 16진수로 변환하는 예를 살펴보겠습니다.
방법은 간단합니다. 수를 16으로 계속 나누면서 나머지를 기록하고, 더 이상 나눌 수 없을 때까지 반복합니다. 그다음 나머지들을 역순으로 읽으면 변환된 결과를 얻을 수 있습니다.
변환 결과 후행 0이 하나 나타나는데, 이 0은 수를 16으로 나누었을 때 나머지가 0이 되는 시점에서 발생합니다.
5040의 소인수분해 결과는 16¹ × 45¹ × 7¹입니다. 즉, 16은 5040을 나머지 0으로 정확히 1번 나눌 수 있으며, 이 값이 곧 후행 0의 개수와 일치합니다. 이러한 원리를 활용하면 후행 0의 개수를 손쉽게 계산할 수 있습니다.
문제 해결 접근 방법
앞서 후행 0의 개수를 구하는 원리를 살펴보았습니다. 여기서 중요한 사실은 16 = 2⁴라는 점입니다. 따라서 N!에서 2의 최고 거듭제곱 지수를 4로 나누면 16의 최고 거듭제곱 지수를 얻을 수 있습니다. 이 계산에 활용되는 것이 바로 르장드르 공식(Legendre's formula)입니다.
C++ 구현 코드
위 접근 방식을 C++로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int main () {
int n = 11;
long long int count = 0;
long long int value, power = 2;
long long int result;
do{
value = n / power;
count += value;
power *= 2;
}
while (value != 0);
// count 변수에 2의 최고 거듭제곱이 저장됨
result = count / 4;
cout << "Number of trailing zeroes in base 16 representation of N : " << result;
}실행 결과
Number of trailing zeroes in base 16 representation of N: 2
코드 설명
- 2의 최고 거듭제곱을 계산해야 하므로 power 변수를 2로 초기화합니다.
- do-while 루프 안에서 르장드르 공식을 구현합니다. n을 power(초기값 2)로 나눈 몫을 count에 누적하고, power에는 계속 2를 곱해 나갑니다.
- 루프가 종료되면 count에 저장된 2의 최고 거듭제곱 값을 4로 나누어 16의 최고 거듭제곱을 구합니다.
- 마지막으로 결과값을 출력합니다.
결론
이 글에서는 르장드르 공식을 활용해 N!의 16진수 표현에서 후행 0의 개수를 구하는 문제를 해결했습니다. 함께 C++ 구현 코드도 살펴보았습니다. 이 코드는 Java, C, Python 등 다른 프로그래밍 언어로도 충분히 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.