정수 값이 담긴 변수 start부터 변수 end까지의 범위가 주어졌을 때, 그 범위 안에 존재하는 팩토리얼 수(factorial number)의 총 개수를 구하는 것이 목표입니다.
팩토리얼 수란?
팩토리얼은 어떤 수부터 1까지의 모든 양의 정수를 차례로 곱한 값이며, 기호 '!'(느낌표)로 나타냅니다. 즉 0!, 1!, 2!, 3!, 4!, ... 형태로 표현하고, 0!과 1!은 항상 1이라는 규칙을 가집니다.
2! = 2 × (2−1) = 2 × 1 = 2
3! = 3 × (3−1) × (2−1) = 3 × 2 × 1 = 6
팩토리얼은 숫자가 조금만 커져도 값이 급격히 증가하기 때문에(예: 5! = 120, 6! = 720), 주어진 범위 안에 들어오는 팩토리얼 수는 생각보다 많지 않습니다. 이 성질을 활용하면 아주 적은 반복 횟수로 문제를 해결할 수 있습니다.
예시
입력 − start = 5, end = 600
출력 − Count of factorial numbers are 3
설명 − 5~600 범위에는 3!(=6), 4!(=24), 5!(=120) 세 개의 팩토리얼 수가 존재합니다.
입력 − start = 1, end = 100
출력 − Count of factorial numbers are 5
설명 − 1~100 범위에는 1(0!, 1!), 2(2!), 6(3!), 24(4!)가 해당됩니다. 이 알고리즘은 fact를 1로 시작해 1!을 두 번 지나가므로 1이 중복 집계되어 총 5로 출력됩니다.
알고리즘 접근 방식
- 범위를 입력받아 변수 start와 end에 저장합니다.
- 팩토리얼 값을 저장할 변수 fact를 1로 초기화하고, 곱해 나갈 숫자를 관리할 임시 변수 i를 준비합니다.
- 첫 번째 루프: fact가 start보다 작은 동안 fact에 i를 곱해 팩토리얼을 만들고 i를 1씩 증가시켜, start 이상이 되는 첫 번째 팩토리얼 수를 찾습니다.
- 두 번째 루프: fact가 end보다 작거나 같은 동안 카운터 변수 r을 증가시키고, fact = fact * i와 i++를 반복해 범위 내 모든 팩토리얼 수를 셉니다.
- 루프가 끝나면 r에는 범위 내 팩토리얼 수의 총 개수가 저장되어 있으므로 이를 반환합니다.
- 결과를 화면에 출력합니다.
팩토리얼은 지수적으로 증가하므로 두 루프의 반복 횟수가 매우 적고, 전체 시간 복잡도는 사실상 O(log end) 수준으로 매우 효율적입니다.
예제 코드
#include <iostream>
using namespace std;
// 범위 내 팩토리얼 수의 개수를 세는 함수
int factorials(int start, int end){
// 1부터 시작해 start 이상인 첫 번째 팩토리얼 수 'fact'를 찾음
int fact = 1, i = 1;
while (fact < start){
fact = fact * i;
i++;
}
// start부터 end 범위 내 팩토리얼 수를 세는 변수 r
int r = 0;
while (fact <= end){
r++;
fact = fact * i;
i++;
}
// 범위 내 팩토리얼 수의 개수를 반환
return r;
}
int main(){
int start = 5, end = 600;
cout << "Count of factorial numbers are " << factorials(start, end);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of factorial numbers are 3