이번에는 백준 3474번 교수가 된 현우 문제를 풀어보았습니다.
이 문제는 N!의 값을 직접 구하는 문제가 아니라,N!의 오른쪽 끝에 붙는 0의 개수를 구하는 문제입니다.
즉, 팩토리얼 자체를 계산하려고 하면 수가 너무 커지기 때문에,
실제로는 0이 만들어지는 원리를 이용해서 접근해야 하는 문제였습니다.
문제 설명
자연수 N이 주어졌을 때, N!의 오른쪽 끝에 있는 0의 개수를 구하면 됩니다.
예를 들어
10! = 3628800이므로 끝의 0은 2개25!는 끝의 0이 더 많음
과 같이, 팩토리얼이 커질수록 뒤에 붙는 0의 개수도 많아집니다.
문제는 테스트 케이스가 여러 개 주어지고,
N의 범위가 매우 크기 때문에 N!을 직접 계산해서는 안 된다는 점입니다.
풀이 아이디어
팩토리얼 뒤에 0이 생기려면 10이 만들어져야 합니다.
그리고 10 = 2 × 5 이므로,
결국 N!의 소인수 분해에서 2와 5가 한 쌍씩 만들어지는 개수를 세면 됩니다.
그런데 N!에서는 항상 2의 개수가 5의 개수보다 많습니다.
따라서 실제로는 5가 몇 개 있는지만 구하면 뒤에 붙는 0의 개수를 알 수 있습니다.
즉, 이 문제는 N!에 포함된 5의 개수를 세는 문제로 바꿀 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<long long> ret;
int N;
int T;
int get_num_cnt(long long target_num, long long num) {
while(num <target_num)
num *= num;
long long cnt = 0;
while(num != 1) {
cnt += (target_num / num);
num /= 5;
}
return cnt;
}
int main() {
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
long long cnt_5 = get_num_cnt(N, 5);
ret.push_back(cnt_5);
}
for (int i = 0; i < ret.size(); i++) {
cout << ret[i] << "\n";
}
return 0;
}풀이 흐름
- 테스트 케이스 개수
T를 입력받는다. - 각 테스트 케이스마다
N을 입력받는다. get_num_cnt(N, 5)를 호출해N!안에 포함된 5의 개수를 구한다.- 구한 값을
ret에 저장한다. - 모든 테스트 케이스에 대해 결과를 출력한다.
구현 포인트
1. 뒤에 붙는 0의 개수는 5의 개수로 결정됨
이 문제에서 가장 중요한 아이디어는 이 부분이었습니다.
N!에서 0 하나가 생기려면 10이 필요하고,10은 2 × 5로 만들어집니다.
그런데 팩토리얼에서는 짝수가 훨씬 많기 때문에,
항상 2의 개수가 5의 개수보다 많습니다.
즉, 부족한 것은 항상 5이고,
결국 뒤에 붙는 0의 개수는 5의 개수와 같다고 볼 수 있습니다.
2. 10! 예시
예를 들어 10!이라면
1 ~ 10사이에서 5의 배수는5,10- 따라서 5의 개수는 2개
즉, 뒤에 붙는 0의 개수도 2개입니다.
3. 25! 예시
25!에서는 단순히 5의 배수 개수만 세면 끝나지 않습니다.
5, 10, 15, 20, 25→ 5의 배수는 5개- 그런데
25 = 5 × 5이므로 5를 하나 더 가집니다
즉, 총 6개의 5가 들어가게 됩니다.
이 때문에 단순히 N / 5만 보는 것이 아니라,N / 25, N / 125 같은 값도 함께 더해주어야 합니다.
4. 일반화한 방식
이걸 일반화하면 N! 안의 5의 개수는
N/5 + N/25 + N/125 + ...형태로 구할 수 있습니다.
즉,
N과 작거나 같은 5의 거듭제곱들을 기준으로- 각 값으로 나눈 몫을 더해가면
전체 5의 개수를 구할 수 있습니다.
코드에서는 이 과정을 get_num_cnt() 함수로 처리했습니다.
while(num != 1) {
cnt += (target_num / num);
num /= 5;
}5. 현재 코드에서의 흐름
코드에서는 먼저 num을 크게 만든 뒤,
다시 5로 나누어가면서 해당 값들에 대해 몫을 더하는 방식으로 구현했습니다.
while(num <target_num)
num *= num;그 다음
cnt += (target_num / num);
num /= 5;를 반복하면서 5의 거듭제곱 단위로 개수를 누적합니다.
즉, 전체적으로는
N! 안에 포함된 5의 개수를 단계적으로 더해가는 방식입니다.
