정수 num이 입력으로 주어졌을 때, 곱 11 × 22 × 33 × … × numnum의 끝에 연속해서 붙는 0(후행 0, trailing zero)의 개수를 구하는 것이 목표입니다.
예시로 이해하기
입력
num=5
출력
(1^1)*(2^2)*(3^3)*(4^4)*.. 의 후행 0 개수: 5
설명
곱에 포함된 2와 5의 개수는 다음과 같습니다.
1^1 × 2^2 × 3^3 × 4^4 × 5^5 = 1^1 × 2^2 × 3^3 × (2^2)^4 × 5^5 → 2는 총 10개, 5는 총 5개 → 최솟값은 5이므로 후행 0은 5개
입력
num=10
출력
(1^1)*(2^2)*(3^3)*(4^4)*.. 의 후행 0 개수: 15
설명
곱에 포함된 2와 5의 개수는 다음과 같습니다.
1^1 × 2^2 × 3^3 × 4^4 × 5^5 × 6^6 × 7^7 × 8^8 × 9^9 × 10^10 = 1^1 × 2^2 × 3^3 × 4^4 × 5^5 × 6^6 × 7^7 × 8^8 × 9^9 × (2×5)^10 → 2는 총 50개, 5는 총 15개 → 최솟값은 15이므로 후행 0은 15개
접근 방법
이 문제는 곱을 이루는 각 수를 소인수분해하여 2와 5의 개수를 세는 방식으로 해결할 수 있습니다. 후행 0은 곱 안에서 2×5 짝 하나당 하나씩 만들어지므로, 전체 곱에서 2의 총 개수와 5의 총 개수 중 더 작은 값이 곧 후행 0의 개수가 됩니다. 특히 각 숫자는 자기 자신만큼 거듭제곱되므로, i가 2(또는 5)로 k번 나누어진다면 해당 소인수는 i×k개만큼 기여한다는 점이 핵심입니다.
- 정수 num을 입력받습니다.
- count_trailing(int num) 함수는 num을 받아 (1^1)*(2^2)*(3^3)*(4^4)*… 의 후행 0 개수를 반환합니다.
- count를 0으로 초기화합니다.
- 2와 5의 개수를 저장할 변수 temp_2 = 0, temp_5 = 0을 선언합니다.
- for 반복문으로 i = 1부터 i ≤ num까지 순회합니다.
- temp에 i를 대입합니다.
- temp가 2로 나누어떨어지는 동안 temp를 절반으로 줄이고, 그때마다 temp_2에 i를 더해 2의 개수를 누적합니다.
- temp가 5로 나누어떨어지는 동안 temp를 5로 나누고, 그때마다 temp_5에 i를 더해 5의 개수를 누적합니다.
- count = min(temp_2, temp_5)로 두 값 중 최솟값을 구합니다.
- count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int count_trailing(int num){
int count = 0;
int temp_2 = 0;
int temp_5 = 0;
for (int i = 1; i <= num; i++){
int temp = i;
while(temp % 2 == 0 && temp > 0){
temp = temp / 2;
temp_2 = temp_2 + i;
}
while (temp % 5 == 0 && temp > 0){
temp = temp / 5;
temp_5 = temp_5 + i;
}
}
count = min(temp_2, temp_5);
return count;
}
int main(){
int num = 5;
cout<<"Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: "<<count_trailing(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5
이 알고리즘은 각 수마다 소인수 2와 5를 제거하는 데 로그 시간이 걸리므로, 전체 시간 복잡도는 O(num log num)입니다. 곱을 직접 계산하지 않고도 후행 0의 개수를 효율적으로 구할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.